Loading…

easyGreedySometimes asked

Priyanka and Toys

Q: How do you solve Priyanka and Toys using the Brute Force — Try Anchoring Windows at Every Subset approach?

When to use it: Mention to acknowledge the search space, then collapse it with sorting. Imagine deciding, for every toy, whether it 'starts' a container window. Any chosen set of starts defines windows `[w, w + 4]`; the set is valid if every toy lies inside at least one window. Search all `2ⁿ` subsets and keep the smallest valid one. **Why it's correct.** Every possible placement of windows is considered (a window only ever needs to start at some toy's weight — starting between toys wastes reach), so the minimum valid subset is the true answer. **Why it's hopeless.** `2ⁿ` subsets is exponential; even `n = 30` is a billion. The constraint allows `n = 100000`, so this never runs. **The structure it reveals.** Notice a window never benefits from starting to the *left* of the smallest toy it must cover — that just wastes reach. So the optimal anchors are always *toys themselves*, processed left to right, each new window opened exactly at the next uncovered toy. That observation removes the search entirely. Time complexity: O(2ⁿ · n). Space complexity: O(n).

Q: How do you solve Priyanka and Toys using the Greedy — Sort and Sweep Fixed-Width Windows (Optimal) approach?

When to use it: The answer they want. Phrase it as 'open a container at the smallest leftover toy and skip everything within 4 of it'. Sort ascending. Sweep left to right. Keep the upper bound `last + 4` of the current container's window (start with `last = −∞`). When a toy's weight exceeds `last + 4`, it can't fit the current window, so open a new container anchored at this toy and set `last` to its weight. Count the opens. **Why anchor at the smallest uncovered toy — the exchange argument.** The leftmost uncovered toy `w` must go into *some* container, whose window is `[base, base + 4]` with `base ≤ w`. Slide that window right until `base = w`. Since every other uncovered toy is `≥ w`, raising `base` to `w` never drops a toy that was already inside (those toys were `≥ base` and now still `≥ w` only if... ) — more precisely, the window `[w, w + 4]` covers at least as many of the *remaining* (uncovered, hence `≥ w`) toys as any window with `base ` boundary.** A toy at exactly `last + 4` differs from the anchor by 4, which is allowed, so it stays in the current window. Using `>=` would wrongly open a new container for it. **Why sorting is required.** The argument 'all remaining toys are ≥ the anchor' only holds if we process in non-decreasing order. Without sorting, a later small toy could appear and break the prefix-covering logic. Time complexity: O(n log n). Space complexity: O(1).

Greedy Algorithms · 22 of 23 · 8 min

Priyanka must distribute n toys into containers. Each toy i has a weight w[i]. A single container can hold any number of toys, as long as the difference between the maximum and minimum weight of the toys it holds is at most 4 — i.e. all its toys fit in some window [base, base + 4].

Return the minimum number of containers needed to hold all the toys.

In plain English

Picture each toy's weight as a point on a number line. A container is an interval of width 4 that you may slide anywhere; it covers every toy point inside it. We want the fewest such intervals to cover all points. Sorting the points and greedily placing each interval starting at the leftmost uncovered point gives the minimum.

Examples

Example 1

Input: w = [1, 2, 3, 21, 7, 12, 14, 21]
Output: 4
Note: Sorted [1,2,3,7,12,14,21,21]. Container 1 anchors at 1 covering ≤5 → holds 1,2,3. Next uncovered 7 → covers ≤11 → holds 7. Next 12 → covers ≤16 → holds 12,14. Next 21 → covers ≤25 → holds 21,21. Total 4.

Example 2

Input: w = [1, 2, 3, 4]
Output: 1
Note: Sorted [1,2,3,4]. Anchor at 1 covers [1,5], which includes 2,3,4. One container.

Example 3

Input: w = [10, 20, 30]
Output: 3
Note: Each gap exceeds 4: anchor 10 covers ≤14 (misses 20), anchor 20 covers ≤24 (misses 30), anchor 30. Three containers.

Constraints

1 ≤ n ≤ 100000
0 ≤ w[i] ≤ 10000
A container holds toys whose weights span at most 4 units (inclusive)

Clarifying questions4First question: Is the window boundary inclusive — does [w, w+4] include w+4?Explore questions

Q1.Is the window boundary inclusive — does [w, w+4] include w+4?
Yes. A toy at exactly w + 4 is within range (difference of 4 is allowed). Use `> last + 4` to start a new window, not `>=`.
Q2.Is there a limit on how many toys or how much total weight a container holds?
No. The only constraint is the 4-unit spread between the lightest and heaviest toy in the container.
Q3.Can weights repeat?
Yes. Duplicates simply fall inside the same window and cost nothing extra.
Q4.Do we need the actual assignment or just the count?
Just the minimum number of containers. The greedy still implicitly defines a valid assignment if asked.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each container can hold all toys whose weights lie in a window `[w, w + 4]` for some chosen base weight `w`. To minimise the number of containers, sort the weights ascending and greedily open a new container at the smallest uncovered weight; it then covers everything up to that weight + 4. Skip every toy within the window and repeat at the next uncovered toy. O(n log n) from the sort.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'fewest containers' as 'fewest fixed-width intervals covering all points', sort, and anchor greedily — plus getting the inclusive boundary (w + 4) right.

Where candidates slip

Centering the window on a weight instead of anchoring at the smallest uncovered one, or using `>=` so a toy exactly at the boundary spawns an unnecessary container.

How to stand out

Give the exchange argument: anchoring the window at the leftmost uncovered toy dominates any later anchor, since moving the anchor left never loses coverage and may gain it.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Anchoring Windows at Every Subset	`O(2ⁿ · n)`	`O(n)`	Mention to acknowledge the search space, then collapse it with sorting.	Read
2	Greedy — Sort and Sweep Fixed-Width Windows (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'open a container at the smallest leftover toy and skip everything within 4 of it'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewWeightsAny toy > w + 4?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Anchoring Windows at Every Subset

TimeO(2ⁿ · n)SpaceO(n)

Mention to acknowledge the search space, then collapse it with sorting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A solution chooses a set of window anchors so that every toy lies in some [anchor, anchor + 4]. Without insight, you might search over which toys start windows.

2Hint 2Explore hint

Try every subset of toys as potential window starts, check that the chosen windows cover all toys, and keep the smallest valid subset.

3Hint 3Explore hint

There are 2ⁿ subsets — only feasible for tiny n. It exists purely to motivate sorting and the leftmost-anchor greedy.

A · Core idea

Imagine deciding, for every toy, whether it 'starts' a container window. Any chosen set of starts defines windows [w, w + 4]; the set is valid if every toy lies inside at least one window. Search all 2ⁿ subsets and keep the smallest valid one.

Why it's correct. Every possible placement of windows is considered (a window only ever needs to start at some toy's weight — starting between toys wastes reach), so the minimum valid subset is the true answer.

Why it's hopeless. 2ⁿ subsets is exponential; even n = 30 is a billion. The constraint allows n = 100000, so this never runs.

The structure it reveals. Notice a window never benefits from starting to the left of the smallest toy it must cover — that just wastes reach. So the optimal anchors are always toys themselves, processed left to right, each new window opened exactly at the next uncovered toy. That observation removes the search entirely.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

w = [1, 2, 3, 4]

anchors {1}

window [1,5] covers 1,2,3,4 → valid, size 1

Statebest = 1

Final result1

C · Code with teaching comments

Reference implementation previewpublic int toysBrute(int[] w) { Arrays.sort(w); int n = w.length, best = n; for (int mask = 1; mask < (1 << n); mask++) { boolean[] covered = new boolean[n];Explore the full code

solution.javaJava

Brute Force — Try Anchoring Windows at Every Subset — reference

2 teaching notes

1
public int toysBrute(int[] w) {
2
    Arrays.sort(w);
3
    int n = w.length, best = n;
4
    for (int mask = 1; mask < (1 << n); mask++) {
5
        boolean[] covered = new boolean[n];
6
        int count = 0;
7
        for (int b = 0; b < n; b++) {
8
            if ((mask & (1 << b)) != 0) {
9
                count++;
10
                for (int j = 0; j < n; j++) {
11
                    // A toy is covered if it lies in the window [anchor, anchor + 4].
12
                    if (w[j] >= w[b] && w[j] <= w[b] + 4) covered[j] = true;
13
                }
14
            }
15
        }
16
        boolean all = true;
17
        for (boolean c : covered) all &= c;
18
        // Track the fewest anchors that cover everything.
19
        if (all) best = Math.min(best, count);
20
    }
21
    return best;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

A window should always be anchored at an actual uncovered toy (anchoring earlier wastes its 4-unit reach). That single observation turns a 2ⁿ subset search into a left-to-right sweep.

ComplexityO(2ⁿ · n) time, O(n) space — 2ⁿ candidate anchor subsets, each checked for full coverage in O(n). Exponential and unusable beyond small n.

E · Edge cases and pitfalls32ⁿ explosion — only for n ≤ ~20.Explore edge cases

Pitfalls

2ⁿ explosion — only for n ≤ ~20.
Anchoring windows between toys wastes reach and never helps.
Forgetting the boundary is inclusive (w + 4 is covered).

03.2

Approach 2 of 2 · Optimal

Greedy — Sort and Sweep Fixed-Width Windows (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'open a container at the smallest leftover toy and skip everything within 4 of it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sort the weights ascending. The smallest toy must be in some container — anchor that container's window at it so it reaches as far right as possible.

2Hint 2Explore hint

That window covers everything up to (smallest weight + 4). Skip all those toys; they cost nothing more.

3Hint 3Explore hint

The next uncovered toy forces a new container. Repeat. Count how many containers you open.

A · Core idea

Sort ascending. Sweep left to right. Keep the upper bound last + 4 of the current container's window (start with last = −∞). When a toy's weight exceeds last + 4, it can't fit the current window, so open a new container anchored at this toy and set last to its weight. Count the opens.

Why anchor at the smallest uncovered toy — the exchange argument. The leftmost uncovered toy w must go into some container, whose window is [base, base + 4] with base ≤ w. Slide that window right until base = w. Since every other uncovered toy is ≥ w, raising base to w never drops a toy that was already inside (those toys were ≥ base and now still ≥ w only if... ) — more precisely, the window [w, w + 4] covers at least as many of the remaining (uncovered, hence ≥ w) toys as any window with base < w, because the only toys a lower base could additionally cover are < w, and there are none left. So anchoring exactly at the smallest uncovered toy is never worse; it covers the longest possible prefix of the remaining toys. Each greedy container therefore covers a maximal run, and any optimal solution can be transformed into this one without increasing the count.

Why the strict `>` boundary. A toy at exactly last + 4 differs from the anchor by 4, which is allowed, so it stays in the current window. Using >= would wrongly open a new container for it.

Why sorting is required. The argument 'all remaining toys are ≥ the anchor' only holds if we process in non-decreasing order. Without sorting, a later small toy could appear and break the prefix-covering logic.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

w = [1, 2, 3, 21, 7, 12, 14, 21]

Array state

open #1 at 1

covers [1,5] → 1,2,3

anchor ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Greedy — Sort and Sweep Fixed-Width Windows (Optimal) — optimal

3 teaching notes

1
public int toys(int[] w) {
2
    // Ascending order so the smallest uncovered toy is always met first.
3
    Arrays.sort(w);
4
    int units = 0;
5
    long last = Long.MIN_VALUE;
6
    for (int weight : w) {
7
        // Strictly greater: a toy at exactly last + 4 is still inside the current
8
        // window.
9
        if (weight > last + 4) {
10
            units++;
11
            // Anchor a fresh window at this uncovered toy; it now covers up to weight +
12
            // 4.
13
            last = weight;
14
        }
15
    }
16
    return units;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Minimum cover by fixed-width intervals = sort + leftmost-anchor sweep. The reusable kernel: when intervals can slide freely, always anchor the next one at the leftmost uncovered point — it dominates every other placement on the remaining points.

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n) and dominates; the single sweep is O(n) with only two scalar variables → O(1) extra space.

E · Edge cases and pitfalls6single toy — One window opens at it → 1 container.Explore edge cases

Edge cases handled

single toyOne window opens at it → 1 container.
all equal weightsFirst toy opens one window covering the rest → 1 container.
weights 4 apart, e.g. [0,4,8]0 covers ≤4 (includes 4); 8 > 4 opens a second → result 2, confirming inclusive boundary.

Pitfalls

Using `>=` instead of `>` — splits a toy that is exactly 4 away into its own container.
Forgetting to sort — the leftmost-anchor argument fails on unsorted input.
Re-anchoring at every toy instead of only uncovered ones — overcounts containers.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int toys(int[] w) { Arrays.sort(w); int units = 0; long last = Long.MIN_VALUE; for (int weight : w) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong boundary comparison

A toy at exactly last + 4 has a weight difference of 4, which is allowed. Using >= opens an unnecessary container.

Explore the code comparison

Don't write this

if weight >= last + 4:
    units += 1
    last = weight

Write this instead

if weight > last + 4:
    units += 1
    last = weight

Forgetting to sort

The greedy relies on always seeing the smallest uncovered toy first. Unsorted input breaks the prefix-covering guarantee.

Explore the code comparison

Don't write this

int units = 0; long last = Long.MIN_VALUE;
for (int weight : w) { if (weight > last + 4) { units++; last = weight; } }

Write this instead

Arrays.sort(w);
int units = 0; long last = Long.MIN_VALUE;
for (int weight : w) { if (weight > last + 4) { units++; last = weight; } }

Anchoring on a fixed window grid

Snapping windows to multiples of 5 (e.g. [0,4],[5,9],…) can split a tight cluster across two containers, overcounting.

Explore the code comparison

Don't write this

units = len({weight // 5 for weight in w})  # fixed grid buckets

Write this instead

w = sorted(w); units = 0; last = float('-inf')
for weight in w:
    if weight > last + 4:
        units += 1; last = weight

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy interval covering: anchor each window at the smallest uncovered point

Code pattern to memorize

sort weights ascending
units = 0
last = -infinity
for w in weights:
    if w > last + 4:        # not covered by the current window
        units += 1
        last = w             # open a new window [w, w + 4]
return units

Rules to remember

1A single container covers a contiguous weight window of size 4: any toys with weight in [w, w + 4] for the chosen base w.
2Sort ascending so you always meet the smallest uncovered toy first.
3Anchor each new window at that smallest uncovered toy w; it greedily covers up to w + 4.
4Use w > last + 4 (strictly greater) — a toy exactly at last + 4 is still inside the window.
5Each container is unlimited in count and weight; the only limit is the 4-unit spread of weights it holds.

Use this pattern when

Cover all points on a line with the fewest fixed-width intervals
Each interval can be positioned freely but has a fixed reach
Sorting reveals that anchoring at the leftmost uncovered point is optimal
Minimising the count of groups, each spanning a bounded range

Choose another pattern when

Intervals have fixed positions you cannot move → interval scheduling, not covering
Capacity is by count or total weight, not by spread → bin packing / knapsack
The window width varies per container → different DP
You must maximise coverage under a fixed number of intervals → a different objective

Interview takeaway

Minimum fixed-width interval cover of points on a line: sort, then greedily anchor each interval at the leftmost uncovered point and jump past its reach. Anchoring at the smallest uncovered point is provably optimal — it covers the most while wasting none of the window to the left.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMinimum fixed-width interval cover of points on a line: sort ascending, anchor each interval at the leftmost uncovered point, jump past its reach. The exchange argument shows the leftmost anchor dominates, making the sweep optimal.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Greedy Florist
Sort-and-assign greedy minimising a weighted sum via the rearrangement inequality.
Jim and the Orders
Sort by a derived key, then read off the order — another sort-first greedy.
Minimum number of arrows to burst balloons
Coming soon
Same fixed/variable interval covering idea — sort by end and greedily cover.
Permuting Two Arrays
Sorting unlocks a per-index greedy check, like the per-window check here.

Same pattern

←

Permuting Two Arrays

Continue · Next problem

Sherlock and the Beast

easyGreedySometimes asked

Priyanka and Toys

Greedy Algorithms · 22 of 23 · 8 min

Return the minimum number of containers needed to hold all the toys.

In plain English

Examples

Example 1

Input: w = [1, 2, 3, 21, 7, 12, 14, 21]
Output: 4
Note: Sorted [1,2,3,7,12,14,21,21]. Container 1 anchors at 1 covering ≤5 → holds 1,2,3. Next uncovered 7 → covers ≤11 → holds 7. Next 12 → covers ≤16 → holds 12,14. Next 21 → covers ≤25 → holds 21,21. Total 4.

Example 2

Input: w = [1, 2, 3, 4]
Output: 1
Note: Sorted [1,2,3,4]. Anchor at 1 covers [1,5], which includes 2,3,4. One container.

Example 3

Input: w = [10, 20, 30]
Output: 3
Note: Each gap exceeds 4: anchor 10 covers ≤14 (misses 20), anchor 20 covers ≤24 (misses 30), anchor 30. Three containers.

Constraints

1 ≤ n ≤ 100000
0 ≤ w[i] ≤ 10000
A container holds toys whose weights span at most 4 units (inclusive)

Clarifying questions4First question: Is the window boundary inclusive — does [w, w+4] include w+4?Explore questions

Q1.Is the window boundary inclusive — does [w, w+4] include w+4?
Yes. A toy at exactly w + 4 is within range (difference of 4 is allowed). Use `> last + 4` to start a new window, not `>=`.
Q2.Is there a limit on how many toys or how much total weight a container holds?
No. The only constraint is the 4-unit spread between the lightest and heaviest toy in the container.
Q3.Can weights repeat?
Yes. Duplicates simply fall inside the same window and cost nothing extra.
Q4.Do we need the actual assignment or just the count?
Just the minimum number of containers. The greedy still implicitly defines a valid assignment if asked.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe 'fewest containers' as 'fewest fixed-width intervals covering all points', sort, and anchor greedily — plus getting the inclusive boundary (w + 4) right.

Where candidates slip

Centering the window on a weight instead of anchoring at the smallest uncovered one, or using `>=` so a toy exactly at the boundary spawns an unnecessary container.

How to stand out

Give the exchange argument: anchoring the window at the leftmost uncovered toy dominates any later anchor, since moving the anchor left never loses coverage and may gain it.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Anchoring Windows at Every Subset	`O(2ⁿ · n)`	`O(n)`	Mention to acknowledge the search space, then collapse it with sorting.	Read
2	Greedy — Sort and Sweep Fixed-Width Windows (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'open a container at the smallest leftover toy and skip everything within 4 of it'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Anchoring Windows at Every Subset

TimeO(2ⁿ · n)SpaceO(n)

Mention to acknowledge the search space, then collapse it with sorting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A solution chooses a set of window anchors so that every toy lies in some [anchor, anchor + 4]. Without insight, you might search over which toys start windows.

2Hint 2Explore hint

Try every subset of toys as potential window starts, check that the chosen windows cover all toys, and keep the smallest valid subset.

3Hint 3Explore hint

There are 2ⁿ subsets — only feasible for tiny n. It exists purely to motivate sorting and the leftmost-anchor greedy.

A · Core idea

Why it's hopeless. 2ⁿ subsets is exponential; even n = 30 is a billion. The constraint allows n = 100000, so this never runs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

w = [1, 2, 3, 4]

anchors {1}

window [1,5] covers 1,2,3,4 → valid, size 1

Statebest = 1

Final result1

C · Code with teaching comments

solution.javaJava

Brute Force — Try Anchoring Windows at Every Subset — reference

2 teaching notes

1
public int toysBrute(int[] w) {
2
    Arrays.sort(w);
3
    int n = w.length, best = n;
4
    for (int mask = 1; mask < (1 << n); mask++) {
5
        boolean[] covered = new boolean[n];
6
        int count = 0;
7
        for (int b = 0; b < n; b++) {
8
            if ((mask & (1 << b)) != 0) {
9
                count++;
10
                for (int j = 0; j < n; j++) {
11
                    // A toy is covered if it lies in the window [anchor, anchor + 4].
12
                    if (w[j] >= w[b] && w[j] <= w[b] + 4) covered[j] = true;
13
                }
14
            }
15
        }
16
        boolean all = true;
17
        for (boolean c : covered) all &= c;
18
        // Track the fewest anchors that cover everything.
19
        if (all) best = Math.min(best, count);
20
    }
21
    return best;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proof

A window should always be anchored at an actual uncovered toy (anchoring earlier wastes its 4-unit reach). That single observation turns a 2ⁿ subset search into a left-to-right sweep.

ComplexityO(2ⁿ · n) time, O(n) space — 2ⁿ candidate anchor subsets, each checked for full coverage in O(n). Exponential and unusable beyond small n.

E · Edge cases and pitfalls32ⁿ explosion — only for n ≤ ~20.Explore edge cases

Pitfalls

2ⁿ explosion — only for n ≤ ~20.
Anchoring windows between toys wastes reach and never helps.
Forgetting the boundary is inclusive (w + 4 is covered).

03.2

Approach 2 of 2 · Optimal

Greedy — Sort and Sweep Fixed-Width Windows (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'open a container at the smallest leftover toy and skip everything within 4 of it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sort the weights ascending. The smallest toy must be in some container — anchor that container's window at it so it reaches as far right as possible.

2Hint 2Explore hint

That window covers everything up to (smallest weight + 4). Skip all those toys; they cost nothing more.

3Hint 3Explore hint

The next uncovered toy forces a new container. Repeat. Count how many containers you open.

A · Core idea

Why the strict `>` boundary. A toy at exactly last + 4 differs from the anchor by 4, which is allowed, so it stays in the current window. Using >= would wrongly open a new container for it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

w = [1, 2, 3, 21, 7, 12, 14, 21]

Array state

open #1 at 1

covers [1,5] → 1,2,3

anchor ↓

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Greedy — Sort and Sweep Fixed-Width Windows (Optimal) — optimal

3 teaching notes

1
public int toys(int[] w) {
2
    // Ascending order so the smallest uncovered toy is always met first.
3
    Arrays.sort(w);
4
    int units = 0;
5
    long last = Long.MIN_VALUE;
6
    for (int weight : w) {
7
        // Strictly greater: a toy at exactly last + 4 is still inside the current
8
        // window.
9
        if (weight > last + 4) {
10
            units++;
11
            // Anchor a fresh window at this uncovered toy; it now covers up to weight +
12
            // 4.
13
            last = weight;
14
        }
15
    }
16
    return units;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n) and dominates; the single sweep is O(n) with only two scalar variables → O(1) extra space.

E · Edge cases and pitfalls6single toy — One window opens at it → 1 container.Explore edge cases

Edge cases handled

single toyOne window opens at it → 1 container.
all equal weightsFirst toy opens one window covering the rest → 1 container.
weights 4 apart, e.g. [0,4,8]0 covers ≤4 (includes 4); 8 > 4 opens a second → result 2, confirming inclusive boundary.

Pitfalls

Using `>=` instead of `>` — splits a toy that is exactly 4 away into its own container.
Forgetting to sort — the leftmost-anchor argument fails on unsorted input.
Re-anchoring at every toy instead of only uncovered ones — overcounts containers.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int toys(int[] w) { Arrays.sort(w); int units = 0; long last = Long.MIN_VALUE; for (int weight : w) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong boundary comparison

A toy at exactly last + 4 has a weight difference of 4, which is allowed. Using >= opens an unnecessary container.

Explore the code comparison

Don't write this

if weight >= last + 4:
    units += 1
    last = weight

Write this instead

if weight > last + 4:
    units += 1
    last = weight

Forgetting to sort

The greedy relies on always seeing the smallest uncovered toy first. Unsorted input breaks the prefix-covering guarantee.

Explore the code comparison

Don't write this

int units = 0; long last = Long.MIN_VALUE;
for (int weight : w) { if (weight > last + 4) { units++; last = weight; } }

Write this instead

Arrays.sort(w);
int units = 0; long last = Long.MIN_VALUE;
for (int weight : w) { if (weight > last + 4) { units++; last = weight; } }

Anchoring on a fixed window grid

Snapping windows to multiples of 5 (e.g. [0,4],[5,9],…) can split a tight cluster across two containers, overcounting.

Explore the code comparison

Don't write this

units = len({weight // 5 for weight in w})  # fixed grid buckets

Write this instead

w = sorted(w); units = 0; last = float('-inf')
for weight in w:
    if weight > last + 4:
        units += 1; last = weight

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy interval covering: anchor each window at the smallest uncovered point

Code pattern to memorize

sort weights ascending
units = 0
last = -infinity
for w in weights:
    if w > last + 4:        # not covered by the current window
        units += 1
        last = w             # open a new window [w, w + 4]
return units

Rules to remember

1A single container covers a contiguous weight window of size 4: any toys with weight in [w, w + 4] for the chosen base w.
2Sort ascending so you always meet the smallest uncovered toy first.
3Anchor each new window at that smallest uncovered toy w; it greedily covers up to w + 4.
4Use w > last + 4 (strictly greater) — a toy exactly at last + 4 is still inside the window.
5Each container is unlimited in count and weight; the only limit is the 4-unit spread of weights it holds.

Use this pattern when

Cover all points on a line with the fewest fixed-width intervals
Each interval can be positioned freely but has a fixed reach
Sorting reveals that anchoring at the leftmost uncovered point is optimal
Minimising the count of groups, each spanning a bounded range

Choose another pattern when

Intervals have fixed positions you cannot move → interval scheduling, not covering
Capacity is by count or total weight, not by spread → bin packing / knapsack
The window width varies per container → different DP
You must maximise coverage under a fixed number of intervals → a different objective

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Greedy Florist
Sort-and-assign greedy minimising a weighted sum via the rearrangement inequality.
Jim and the Orders
Sort by a derived key, then read off the order — another sort-first greedy.
Minimum number of arrows to burst balloons
Coming soon
Same fixed/variable interval covering idea — sort by end and greedily cover.
Permuting Two Arrays
Sorting unlocks a per-index greedy check, like the per-window check here.

Same pattern

←

Permuting Two Arrays

Continue · Next problem

Sherlock and the Beast