Partition Array Such That Maximum Difference Is K
Real-world version: Fewest Crates for the RodsThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def partition_array(nums: list[int], k: int) -> int:public int partitionArray(int[] nums, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's