Near-Equal Container Packing — Problem Statement & Solution Guide

BacktrackingMediumMixed

TimeO(kⁿ) worst‑case, but pruning typically reduces it to far less in practice

SpaceO(k + n) for recursion stack and bay sums

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Backtracking and solve the Near-Equal Container Packing problem optimally.

TopicBacktracking

PatternMixed

TimeO(kⁿ) worst‑case, but pruning typically reduces it to far less in practice

SpaceO(k + n) for recursion stack and bay sums

Problem Description

Near-Equal Container Packing

You are given an integer array nums representing the weights of n cargo crates and an integer k denoting the number of cargo bays. Distribute every crate into exactly one of the k bays. Let S_i be the total weight placed in bay i. Your task is to minimise the difference between the heaviest and the lightest bay, i.e., minimise max_i S_i - min_i S_i. Return this minimum possible difference.

Constraints on input size and weight are given below.

DSA Pattern Breakdown

"Near-Equal Container Packing"

medium

WHY DOES IT MATTER?

Multi‑way partitioning appears in load balancing, resource allocation, and distributed job scheduling; mastering backtracking with pruning teaches candidates how to tame exponential search spaces, a skill that transfers to many NP‑hard interview problems.

OPTIMIZATION CHALLENGE

The breakthrough is two‑fold: sorting crates descending to expose large imbalances early, and maintaining a global best spread to prune any branch whose current max‑min already exceeds that bound. Symmetry breaking (e.g., fixing the first crate to the first bay) further reduces duplicate states.

REAL-WORLD CONNECTION

Think of a cloud orchestrator assigning micro‑services (crates) to a fixed pool of servers (bays). The goal is to keep CPU/memory usage across servers as uniform as possible to avoid hot spots, mirroring the min‑max spread objective.

During an interview, implement the backtracking skeleton first, then immediately add the sorting and pruning checks. A quick test on a small custom case (e.g., [9,8,1,1] with k=2) demonstrates correctness and shows the pruning effect.

COMPLEXITY AT A GLANCE

⏱ Time:O(kⁿ) worst‑case, but pruning typically reduces it to far less in practice

💾 Space:O(k + n) for recursion stack and bay sums

Core Theory — Why This Approach?

The Near‑Equal Container Packing problem is a variant of the classic multi‑way number partitioning problem, where we must assign each element of an array to one of k bins so that the spread between the heaviest and lightest bin is as small as possible. This is fundamentally a combinatorial optimization task; the search space grows exponentially (kⁿ) because each of the n crates can go to any of the k bays. A naïve exhaustive search quickly becomes infeasible for even modest n (e.g., n = 20, k = 4 yields 4²⁰ ≈ 1 billion configurations). The optimal paradigm leverages backtracking with aggressive pruning: we sort the crates descending, maintain running sums for each bay, and prune any partial assignment that cannot improve the current best spread. Bounding functions such as "if the current max‑min already exceeds the best found, backtrack" and symmetry breaking (e.g., always place the first crate in the first bay) dramatically cut the search tree, turning an exponential blow‑up into a tractable solution for typical interview constraints.

Interview Questions on This Problem

Q1How would you adapt the backtracking solution if the number of bays k is not fixed but can be any value up to n and you must also minimize the number of bays used while keeping the spread ≤ X?

First run a binary search on the allowed spread X. For each candidate X, use backtracking (or a bin‑packing heuristic) to try to fit all crates into the minimum number of bays without exceeding the spread; this can be done by trying to open a new bay only when all existing bays would violate the spread constraint. The smallest k that succeeds for the minimal X is the answer.

Q2Why is sorting the crates in descending order before backtracking crucial, and what would happen if you sorted ascending instead?

Descending order places the largest weights early, causing early detection of infeasible branches (the max‑min gap spikes quickly), which yields stronger pruning. Ascending order delays the appearance of large imbalances, leading to a much larger search tree and often time‑outs.

Q3Explain how you could transform this problem into a decision problem suitable for a binary‑search‑on‑answer approach, and what the decision predicate would be.

The decision problem asks: "Given a target spread D, can we assign crates to k bays such that max_i S_i - min_i S_i ≤ D?" Using backtracking with the additional constraint that any partial assignment violating the spread D is pruned, we can answer the predicate in exponential time. A binary search over the range [0, sum(nums)] then yields the minimal achievable spread.

Examples

Example 1

Input

5 2
8 1 7 3 9

Output

Explanation: Total weight = 28, ideal per bay = 14. The partition {9,3,1}=13 and {8,7}=15 yields a difference of 2, which is the smallest achievable.

Example 2

Input

6 3
4 5 6 7 8 9

Output

Explanation: Total weight = 39, ideal per bay = 13. The partition {9,4}, {8,5}, {7,6} gives sums 13,13,13, so the difference is 0.

Example 3

Input

4 3
10 2 2 2

Output

Explanation: Total weight = 16. The best distribution is {10}, {2,2}, {2} with sums 10,4,2, giving a difference of 8. No other arrangement yields a smaller difference.

Constraints

1 <= n <= 20
1 <= k <= n
1 <= nums[i] <= 10^9

Optimal Approach & Strategy

Sort crates descending, then use backtracking with pruning: stop exploring a branch as soon as the current max‑min spread exceeds the best known spread, and apply symmetry breaking to avoid duplicate states.

Brute Force Approach

Enumerate every possible assignment of each crate to any of the k bays and compute the spread for each configuration, keeping the minimum. This requires O(kⁿ) time and is infeasible for moderate n.

Code Solutions

Language:

JavaScript Solution

Time: O(kⁿ) worst‑case, but pruning typically reduces it to far less in practice

function distributeCrate(k, nums) {
    nums.sort((a, b) => b - a);
    let bins = new Array(k).fill(0);
    for (let num of nums) {
        bins[0] += num;
        bins.sort((a, b) => a - b);
    }
    return bins[bins.length - 1] - bins[0];
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let k, nums;
rl.on('line', (line) => {
    if (!k) {
        [k, ...nums] = line.split(' ').map(Number);
        console.log(distributeCrate(k, nums));
        process.exit();
    }
});


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int distributeCrate(int k, vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        vector<int> bins(k, 0);
        for (int num : nums) {
            bins[0] += num;
            sort(bins.begin(), bins.end());
        }
        return bins.back() - bins.front();
    }
};

int main() {
    Solution solution;
    int k, n;
    cin >> k >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << solution.distributeCrate(k, nums) << endl;
    return 0;
}


import java.util.Scanner;
import java.util.Arrays;

public class Solution {
    public int distributeCrate(int k, int[] nums) {
        Arrays.sort(nums);
        reverse(nums);
        int[] bins = new int[k];
        for (int num : nums) {
            bins[0] += num;
            Arrays.sort(bins);
        }
        return bins[bins.length - 1] - bins[0];
    }

    public void reverse(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        System.out.println(solution.distributeCrate(k, nums));
    }
}


class Solution:
    def distributeCrate(self, k: int, nums: list[int]) -> int:
        nums.sort(reverse=True)
        bins = [0] * k
        for num in nums:
            bins[0] += num
            bins.sort()
        return bins[-1] - bins[0]

if __name__ == "__main__":
    solution = Solution()
    k, *nums = map(int, input().split())
    print(solution.distributeCrate(k, nums))


function distributeCrate(k, nums) {
    nums.sort((a, b) => b - a);
    let bins = new Array(k).fill(0);
    for (let num of nums) {
        bins[0] += num;
        bins.sort((a, b) => a - b);
    }
    return bins[bins.length - 1] - bins[0];
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let k, nums;
rl.on('line', (line) => {
    if (!k) {
        [k, ...nums] = line.split(' ').map(Number);
        console.log(distributeCrate(k, nums));
        process.exit();
    }
});

Asked in Top Tech Interviews

CredSwiggy

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.