0152EasyArrayGreedy

Blade Spacing in the Rack

Tracked in this browser only

Trains the technique from

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 server rack is one straight row of slots, given to you as the array slots. An entry of 1 means that slot already carries a blade and an entry of 0 means the slot is bare.

Airflow rules forbid two blades in slots that touch, and the rack as handed over already respects that, so no two 1 entries sit side by side.

The data centre wants extra further blades racked. A blade may go into a bare slot only when the slots touching it are bare as well; a slot at either end of the row has just one neighbour to satisfy. As soon as a blade goes in, that slot counts as carrying a blade for everything installed afterwards.

Return true when all extra blades can be racked and false when they cannot. Racking only some of them does not count as success. When extra is 0 there is nothing to install and the answer is true.

Examples

Example 1

Input: slots = [0, 0, 1, 0, 0, 0], extra = 2
Output: true

One blade fits in slot 0, which blocks slot 1, and slot 3 is already blocked by the blade in slot 2. Slot 4 is still free on both sides, so the second blade fits there.

Example 2

Input: slots = [0, 0, 1, 0, 0, 0], extra = 3
Output: false

The same rack has room for two blades at most, so a request for three cannot be met.

Example 3

Input: slots = [0], extra = 1
Output: true

A row of one bare slot has no neighbouring slot at all, so nothing blocks the single blade.

Constraints

1 <= slots.length <= 2 * 10^4
slots[i] is 0 or 1.
No two slots carrying a blade touch each other in the rack as given.
0 <= extra <= slots.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 blade_spacing(slots: list[int], extra: int) -> bool:

Java

public boolean bladeSpacing(int[] slots, int extra)

The intended approach

Time O(n)Space O(1)

Sweep the row once and rack a blade at the earliest slot that allows one. Filling the earliest legal slot never costs a later opportunity, because leaving it bare would only push the same run of bare slots along without opening a new one, so the sweep reaches the largest number of blades the rack can hold. Carry a single flag for whether the slot just passed ends up occupied, check the slot ahead directly, and stop the moment enough blades are placed.

Pythonentry point: blade_spacing

def blade_spacing(slots, extra):
    # Time: O(n) -- one sweep of the row, cut short once enough blades fit.
    # Space: O(1) -- two counters and a flag; the row itself is never copied.
    if extra <= 0:
        return True
    n = len(slots)
    racked = 0
    behind_busy = False
    for i in range(n):
        if slots[i] == 1:
            behind_busy = True
            continue
        ahead_busy = i + 1 < n and slots[i + 1] == 1
        if not behind_busy and not ahead_busy:
            racked += 1
            if racked >= extra:
                return True
            behind_busy = True
        else:
            behind_busy = False
    return racked >= extra

The obvious version

Work out the true maximum number of blades the rack can hold by trying both choices at every bare slot with a recursion over the row, remembering results per position and neighbour state, then compare that maximum with the request.

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_blade_spacing(slots, extra):
    n = len(slots)
    seen = {}

    def most(i, behind_busy):
        if i == n:
            return 0
        key = (i, behind_busy)
        if key in seen:
            return seen[key]
        if slots[i] == 1:
            answer = most(i + 1, True)
        else:
            answer = most(i + 1, False)
            if not behind_busy and (i + 1 >= n or slots[i + 1] == 0):
                withblade = 1 + most(i + 1, True)
                if withblade > answer:
                    answer = withblade
        seen[key] = answer
        return answer

    return extra <= most(0, False)

How this problem was checked

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