0897MediumArrayGreedySorting

Fewest Crates for the Rods

Tracked in this browser only

Trains the technique from

LeetCode 2294Partition Array Such That Maximum Difference Is K

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A pile of rods has lengths nums. Rods are packed into crates, and every rod goes into exactly one crate.

A crate is sound when the longest and shortest rod inside it differ by at most k. A crate may hold rods from anywhere in the pile, not just neighbouring ones.

Return the fewest sound crates that hold the whole pile.

Examples

Example 1

Input: nums = [27, 3, 14, 8, 21, 5], k = 6
Output: 3

Sorted, the lengths run 3, 5, 8, 14, 21, 27. The first crate takes 3, 5 and 8, since 8 is six above 3. The next takes 14 alone, because 21 is seven above it, and the last takes 21 and 27.

Example 2

Input: nums = [10, 20, 30, 40], k = 10
Output: 2

A gap of exactly ten is allowed, so 10 and 20 share a crate and 30 and 40 share another.

Example 3

Input: nums = [1, 2, 3, 4, 5], k = 0
Output: 5

With no slack at all, every distinct length needs its own crate.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
0 <= k <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def partition_array(nums: list[int], k: int) -> int:

Java

public int partitionArray(int[] nums, int k)

The intended approach

Time O(n log n) for n rods, the sort being the cost.Space O(n) for the sorted lengths.

Since a crate may draw from anywhere in the pile, only the lengths matter and not their order, so sort them. In sorted order a sound crate is a stretch of consecutive lengths, because if a crate holds two lengths it may as well hold everything between them: that changes neither the longest nor the shortest rod inside it, so the crate stays sound and the rods in between need no crate of their own. That leaves cutting the sorted list into as few stretches as possible, each spanning at most `k`. Walk the sorted lengths holding the shortest rod of the crate being filled, and open a new crate the moment a length exceeds that shortest by more than `k`. Opening later is never possible and opening earlier never helps, so this uses the fewest crates.

Pythonentry point: partition_array

def partition_array(nums, k):
    order = sorted(nums)
    crates = 0
    shortest = None
    for v in order:
        if shortest is None or v - shortest > k:
            crates += 1
            shortest = v
    return crates

The obvious version

Hand the rods out one at a time, trying each rod in every crate opened so far as well as in a fresh one, and keep the smallest number of crates any of those arrangements reaches. Explores every way of grouping the pile and never sorts anything.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_partition_array(nums, k):
    n = len(nums)
    best = [n]

    def place(at, groups):
        if len(groups) >= best[0]:
            return
        if at == n:
            best[0] = len(groups)
            return
        v = nums[at]
        for g in range(len(groups)):
            low, high = groups[g]
            new_low = low if low < v else v
            new_high = high if high > v else v
            if new_high - new_low <= k:
                groups[g] = (new_low, new_high)
                place(at + 1, groups)
                groups[g] = (low, high)
        groups.append((v, v))
        place(at + 1, groups)
        groups.pop()

    place(0, [])
    return best[0]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in