0877MediumArrayHash TableGreedySorting

Splitting the Reels Into Runs

Tracked in this browser only

Trains the technique from

LeetCode 1296Divide Array in Sets of K Consecutive Numbers

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 batch of film reels is logged as nums, where nums[i] is the length of reel i in metres. Every reel must go into a canister, and each canister must hold exactly k reels whose lengths are k consecutive whole numbers, in some order.

Return true when the batch can be split up that way, and false otherwise.

Examples

Example 1

Input: nums = [4, 5, 6, 7, 8, 9], k = 3
Output: true

One canister takes the reels of 4, 5 and 6 metres and the other takes 7, 8 and 9, and each holds three consecutive lengths.

Example 2

Input: nums = [7, 8, 9, 7, 8, 10], k = 3
Output: false

One canister must take the reels of 7, 8 and 9 metres, which leaves 7, 8 and 10, and those three are not consecutive.

Example 3

Input: nums = [2, 2, 3, 3, 4, 4], k = 3
Output: true

Two canisters each take reels of 2, 3 and 4 metres.

Constraints

1 <= nums.length <= 10^5
1 <= k <= 100000
1 <= nums[i] <= 10^9
k is at most nums.length

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 split_into_runs(nums: list[int], k: int) -> bool:

Java

public boolean splitIntoRuns(int[] nums, int k)

The intended approach

Time O(d log d) for d distinct lengths, dominated by ordering them.Space O(d) for the tally.

The shortest reel left over has to open a canister, because nothing shorter remains to sit below it in a run. So tally the lengths, walk them in increasing order, and whenever a length still has reels left, open that many canisters starting there and take one reel of each of the next `k - 1` lengths from each of them. Any shortfall means the batch cannot be split. Since a length is only ever opened once, the walk settles every canister without any searching.

Pythonentry point: split_into_runs

def split_into_runs(nums, k):
    if len(nums) % k != 0:
        return False
    tally = {}
    for length in nums:
        tally[length] = tally.get(length, 0) + 1
    for length in sorted(tally):
        need = tally.get(length, 0)
        if need == 0:
            continue
        for step in range(k):
            here = length + step
            if tally.get(here, 0) < need:
                return False
            tally[here] -= need
    return True

The obvious version

Hold the reels in a plain list. Repeatedly take the shortest one left, then look for and remove one reel of each of the next lengths in turn, failing as soon as one is missing. Removes reels one at a time rather than a whole canister's worth at once.

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_split_into_runs(nums, k):
    if len(nums) % k != 0:
        return False
    pool = sorted(nums)
    while pool:
        base = pool[0]
        for step in range(k):
            want = base + step
            if want in pool:
                pool.remove(want)
            else:
                return False
    return True

How this problem was checked

Reference solution executed against 12 test cases — 12 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