Loading…

easyGreedySometimes asked

Max Min

Q: How do you solve Max Min using the Brute Force — Check Every k-Subset approach?

When to use it: Mention it to expose the combinatorial blow-up, then use the 'contiguous after sorting' insight to kill it. The literal reading: enumerate every subset of exactly k elements, compute `max − min` for each, and remember the smallest. **Why it's the honest baseline.** 'Choose k of n to minimise a function of the chosen set' is a subset-optimisation problem, and the no-insight answer is to try every subset. Stating it shows you understand the search space before you shrink it. **Why it's unusable.** The count of k-subsets is `C(n, k)`. At `n = 10⁵` and `k = n/2` that number dwarfs anything computable. Even modest sizes (n = 40, k = 20) give over a hundred billion subsets. The brute force is correct and completely impractical. **The observation that rescues us.** The score ignores the middle k−2 elements entirely. So for any chosen min and max, filling the middle with whatever lies between them costs nothing. That means the *best* set for a given spread is simply 'all elements between two chosen endpoints' — and to make k of them fit in the tightest span, the endpoints should be as close as possible with exactly k values between them inclusive. Sort the array and that set is a contiguous window. Time complexity: O(C(n,k) · k). Space complexity: O(k).

Greedy Algorithms · 9 of 23 · 8 min

Given an array of integers arr and a number k, you must create an array of length k from elements of arr such that its unfairness is minimised.

The unfairness of an array is defined as max(array) − min(array). Return the minimum possible unfairness over all length-k subsets of arr.

In plain English

We pick k of the n numbers. The score is only the gap between the largest and smallest picked — the k−2 in between contribute nothing. To make that gap small, the k numbers must be packed as closely as possible on the number line, which means contiguous once sorted.

Examples

Example 1

Input: arr = [10, 100, 300, 200, 1000, 20, 30], k = 3
Output: 20
Note: Sorted: [10,20,30,100,200,300,1000]. Window [10,20,30] has gap 30−10 = 20, the smallest of any width-3 window.

Example 2

Input: arr = [1, 2, 3, 4, 10, 20, 30, 40, 100, 200], k = 4
Output: 3
Note: Sorted already. Window [1,2,3,4] gives 4−1 = 3, beating every other width-4 window.

Example 3

Input: arr = [1, 2, 1, 2, 1], k = 2
Output: 0
Note: Sorted: [1,1,1,2,2]. Window [1,1] gives gap 0 — equal values make unfairness vanish.

Constraints

2 ≤ n ≤ 10⁵ (length of arr)
2 ≤ k ≤ n
0 ≤ arr[i] ≤ 10⁹
Elements may repeat

Clarifying questions4First question: Does unfairness depend on anything besides the min and max of the chosen set?Explore questions

Q1.Does unfairness depend on anything besides the min and max of the chosen set?
No — it's exactly max − min. The middle values are irrelevant, which is the key simplification.
Q2.Do the chosen elements need to keep their original positions?
No. We choose a subset by value, so we're free to sort the array first.
Q3.Can elements repeat, and could the answer be 0?
Yes. If k equal values exist, the window gap is 0 — the minimum possible unfairness.
Q4.Is k guaranteed to be at most n?
Yes, 2 ≤ k ≤ n, so at least one window of size k always exists.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Unfairness = max − min of the chosen set, so a tight (min, max) gap means the chosen numbers must be close together — which only happens when they're contiguous in sorted order. Sort the array, then slide a window of size k and return the smallest `arr[i+k-1] − arr[i]`. O(n log n) from the sort, O(n) for the slide.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise the chosen numbers must be contiguous after sorting — that the middle elements are irrelevant and only the window endpoints drive the cost.

Where candidates slip

Trying to cleverly pick non-adjacent numbers, or comparing every pair O(n²) instead of seeing that sorting reduces it to k-width windows.

How to stand out

Prove contiguity: if the optimal set skipped a sorted element lying between its min and max, swapping that element in never widens the gap — so a contiguous window is always at least as good.

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 — Check Every k-Subset	`O(C(n,k) · k)`	`O(k)`	Mention it to expose the combinatorial blow-up, then use the 'contiguous after sorting' insight to kill it.	Read
2	Sort + Sliding Window of Size k (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'after sorting, the best k are contiguous, so slide a width-k window'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPick k numbers, minimise max − minDoes cost depend on middle values?No, only endpointsExplore 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 — Check Every k-Subset

TimeO(C(n,k) · k)SpaceO(k)

Mention it to expose the combinatorial blow-up, then use the 'contiguous after sorting' insight to kill it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The unfairness of a set is just its max minus its min. How many ways are there to choose k of the n numbers?

2Hint 2Explore hint

Enumerate every k-element subset, compute its max − min, and keep the smallest. Correct, but the number of subsets is C(n, k), which explodes.

3Hint 3Explore hint

Before optimising, ask: does the choice of the k−2 middle elements ever affect the score? If not, can you avoid trying every combination?

A · Core idea

The literal reading: enumerate every subset of exactly k elements, compute max − min for each, and remember the smallest.

Why it's the honest baseline. 'Choose k of n to minimise a function of the chosen set' is a subset-optimisation problem, and the no-insight answer is to try every subset. Stating it shows you understand the search space before you shrink it.

Why it's unusable. The count of k-subsets is C(n, k). At n = 10⁵ and k = n/2 that number dwarfs anything computable. Even modest sizes (n = 40, k = 20) give over a hundred billion subsets. The brute force is correct and completely impractical.

The observation that rescues us. The score ignores the middle k−2 elements entirely. So for any chosen min and max, filling the middle with whatever lies between them costs nothing. That means the best set for a given spread is simply 'all elements between two chosen endpoints' — and to make k of them fit in the tightest span, the endpoints should be as close as possible with exactly k values between them inclusive. Sort the array and that set is a contiguous window.

B · Visual dry run

Interactive dry run

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

arr = [1, 4, 7, 2], k = 2

{1,4}

4 − 1 = 3

Statebest = 3

Final result1

C · Code with teaching comments

Reference implementation previewpublic int maxMin(int k, int[] arr) { int n = arr.length; int best = Integer.MAX_VALUE; int[] combo = new int[k]; best = combine(arr, k, 0, 0, combo, best);Explore the full code

solution.javaJava

Brute Force — Check Every k-Subset — reference

2 teaching notes

1
public int maxMin(int k, int[] arr) {
2
    int n = arr.length;
3
    int best = Integer.MAX_VALUE;
4
    int[] combo = new int[k];
5
    best = combine(arr, k, 0, 0, combo, best);
6
    return best;
7
}
8
 
9
private int combine(int[] arr, int k, int start, int depth, int[] combo, int best) {
10
    // A full k-element combination is built — score it by max − min.
11
    if (depth == k) {
12
        int mn = combo[0], mx = combo[0];
13
        for (int v : combo) { mn = Math.min(mn, v); mx = Math.max(mx, v); }
14
        return Math.min(best, mx - mn);
15
    }
16
    for (int i = start; i < arr.length; i++) {
17
        combo[depth] = arr[i];
18
        // Recurse choosing the next element after i, so each subset is generated once.
19
        best = combine(arr, k, i + 1, depth + 1, combo, best);
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(C(n,k) · k) timeO(k) spaceOpen the invariant and proofExplore the proof

Because only the endpoints matter, the middle elements are free filler. The cheapest way to gather k values with a small endpoint gap is to take them already adjacent on the number line — i.e. contiguous in sorted order. That collapses C(n,k) subsets to just n−k+1 windows.

ComplexityO(C(n,k) · k) time, O(k) space — There are C(n, k) subsets, and scanning each for its min and max costs O(k). For moderate n and k this is astronomically large.

E · Edge cases and pitfalls3Generating ordered tuples instead of combinations — multiplies the work by k! for no benefit.Explore edge cases

Pitfalls

Generating ordered tuples instead of combinations — multiplies the work by k! for no benefit.
Believing it's viable for large n — C(n,k) is far beyond brute-forceable.
Recomputing min/max from scratch per subset when you could prune — still exponential overall.

03.2

Approach 2 of 2 · Optimal

Sort + Sliding Window of Size k (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'after sorting, the best k are contiguous, so slide a width-k window'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unfairness only sees the min and max of your pick. If you sort the array, where would a tightly packed group of k numbers live?

2Hint 2Explore hint

Sort ascending. Any contiguous block of k sorted values has its min at the left end and its max at the right end, so its spread is just `arr[i + k - 1] − arr[i]`.

3Hint 3Explore hint

Slide that window across all valid start indices i (from 0 to n − k) and keep the smallest endpoint gap. One pass after the sort.

A · Core idea

Sort arr ascending. Then for each window of k consecutive sorted elements starting at index i, the spread is arr[i + k - 1] − arr[i] — the right endpoint minus the left, because a sorted slice has its extremes at its ends. Slide i from 0 to n − k and keep the minimum spread.

Why the optimal k are contiguous in sorted order — the proof. Sort the array. Suppose an optimal solution picks k values whose minimum sits at sorted index i and maximum at sorted index j, with j − i ≥ k − 1 (it must span at least k positions). If j − i > k − 1, then strictly between i and j there are more than k − 2 elements, so the chosen set skipped at least one sorted element lying inside [arr[i], arr[j]]. Replace any chosen non-endpoint with that skipped interior element: the min and max are unchanged (the swap stays within the span), so the unfairness is unchanged. Repeat until the chosen indices are exactly i, i+1, …, i+k−1 — a contiguous window with the same unfairness. Hence some contiguous window is always at least as good as any optimal set. We only need to check contiguous windows.

Why the gap is just last minus first. Within a sorted window arr[i..i+k-1], every element is ≥ arr[i] and ≤ arr[i+k-1]. So the min is the first element and the max is the last — no need to scan the window, the spread is a single subtraction.

Why the loop bound is `i ≤ n − k`. The last legal window starts where its right end i + k − 1 equals n − 1, i.e. i = n − k. Stopping at n − k exclusive would drop that final window — a classic off-by-one that can hide the true minimum when it lives at the tail.

Why sorting is mandatory, not optional. The entire contiguity argument is a statement about sorted order. On an unsorted array, 'consecutive positions' have no relation to closeness in value, and the window gap is meaningless. The O(n log n) sort isn't overhead — it's what makes the linear slide correct.

B · Visual dry run

Interactive dry run

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

arr = [10, 100, 300, 200, 1000, 20, 30], k = 3

Array state

i=0

[10,20,30] → gap 20 (best)

lo ↓

[0]

[1]

hi ↓

[2]

100

[3]

200

[4]

300

[5]

1000

[6]

Current pointerResolved stateNot processed

Final result20

C · Code with teaching comments

solution.javaJava

Sort + Sliding Window of Size k (Optimal) — optimal

3 teaching notes

1
public int maxMin(int k, int[] arr) {
2
    // Sorting is what makes the optimal k contiguous — the whole method depends on it.
3
    Arrays.sort(arr);
4
    int best = Integer.MAX_VALUE;
5
    // i + k − 1 is the window's right end; the condition keeps it in bounds, including
6
    // the last window.
7
    for (int i = 0; i + k - 1 < arr.length; i++) {
8
        // Spread of a sorted window is last minus first — no inner scan needed.
9
        best = Math.min(best, arr[i + k - 1] - arr[i]);
10
    }
11
    return best;
12
}

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

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

The middle elements being irrelevant is the crux: it lets you treat the chosen set as 'pick two endpoints k−1 apart in sorted order'. Once framed that way, you're minimising the gap between elements exactly k−1 apart, which is a textbook fixed-width window. Recognising 'cost = function of extremes only' is the trigger to sort and slide.

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n) and dominates. The window slide visits each start index once, O(n − k) = O(n), using a couple of scalars → O(1) extra space.

E · Edge cases and pitfalls6arr = [1, 2, 1, 2, 1], k = 2 — Sorted [1,1,1,2,2]; window [1,1] yields gap 0 — the minimum possible.Explore edge cases

Edge cases handled

arr = [1, 2, 1, 2, 1], k = 2Sorted [1,1,1,2,2]; window [1,1] yields gap 0 — the minimum possible.
k = nOnly one window (the whole sorted array); answer is arr[n−1] − arr[0].
all equal valuesEvery window gap is 0, so the answer is 0.

Pitfalls

Forgetting to sort — window gaps on an unsorted array are meaningless.
Looping i to n − k exclusive — drops the final window and can miss the true minimum.
Scanning each window for min/max — unnecessary; the endpoints already are the extremes.

Practice

Try the solution yourself

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

Editable code previewpublic int maxMin(int k, int[] arr) { Arrays.sort(arr); int best = Integer.MAX_VALUE; for (int i = 0; i + k - 1 < arr.length; i++) { best = Math.min(best, arr[i + k - 1] - arr[i]);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.

Off-by-one on the window bound

The last valid window starts at n − k. Looping i < n − k (exclusive) skips it, and the global minimum can live in that final window.

Explore the code comparison

Don't write this

for (int i = 0; i < arr.length - k; i++) {
    best = Math.min(best, arr[i + k - 1] - arr[i]);
}

Write this instead

for (int i = 0; i + k - 1 < arr.length; i++) {
    best = Math.min(best, arr[i + k - 1] - arr[i]);
}

Forgetting to sort

Contiguity only implies closeness in value after sorting. On the raw array, adjacent positions can hold wildly different numbers, so window gaps are nonsense.

Explore the code comparison

Don't write this

return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Write this instead

arr.sort()
return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Taking the gap as a fixed pair instead of sliding

Comparing only the first and last of the whole sorted array ignores tighter interior windows — you must slide across all start indices.

Explore the code comparison

Don't write this

arr.sort()
return arr[k - 1] - arr[0]

Write this instead

arr.sort()
return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort + fixed-size sliding window minimising the endpoints' gap

Code pattern to memorize

sort(arr)
best = ∞
for i in 0 .. n-k:
    best = min(best, arr[i + k - 1] - arr[i])
return best

Rules to remember

1Unfairness depends only on the chosen set's min and max — the k−2 middle values don't matter, so cluster them tightly.
2After sorting, the optimal k numbers are always contiguous — never skip elements to build the set.
3The window's gap is just arr[i + k - 1] − arr[i] (last minus first), since the slice is sorted.
4Loop i from 0 to n − k inclusive — off-by-one here drops the last valid window.
5Sort first or none of this holds — the contiguity argument is purely a property of sorted order.

Use this pattern when

Choose a subset of fixed size k to minimise (or bound) the spread between its extremes
The objective depends only on the min and max of the chosen elements
Elements can be freely reordered (no positional constraint)
You can afford an O(n log n) sort

Choose another pattern when

The objective depends on the actual middle values (sum, variance) → not just endpoints, rethink
You must keep original positions / contiguity in the input array → can't sort
k is not fixed (choose any size) → different problem entirely
You need the actual subset, not just the spread → still works, track the window index

Interview takeaway

When a cost depends only on the extremes of a chosen fixed-size set, sort and slide a width-k window. 'Sort then minimise adjacent/window gaps' is the same move behind Minimum Absolute Difference and many spread-minimisation problems.

Continue

Transfer the pattern to another problem

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

Transferable patternSort + fixed-width sliding window for spread minimisation. Recognise it when a cost depends only on the extremes of a fixed-size chosen set — sort, then minimise arr[i+k-1] − arr[i] across windows. Minimum Absolute Difference is the k = 2 instance.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Minimum Absolute Difference in an Array
Coming soon
Special case with window size 2 — sort and scan adjacent pairs.
Mark and Toys
Another sort-then-prefix greedy, here maximising count under a budget.
Maximize Distance to Closest Person
Coming soon
Scan gaps after fixing positions — gap-minimising/maximising cousin.
Smallest Range Covering K Lists
Coming soon
Generalises window-min-spread to k separate sorted lists with a heap.

Same pattern

←

Mark and Toys

Continue · Next problem

Activity Selection

easyGreedySometimes asked

Max Min

Greedy Algorithms · 9 of 23 · 8 min

Given an array of integers arr and a number k, you must create an array of length k from elements of arr such that its unfairness is minimised.

The unfairness of an array is defined as max(array) − min(array). Return the minimum possible unfairness over all length-k subsets of arr.

In plain English

Examples

Example 1

Input: arr = [10, 100, 300, 200, 1000, 20, 30], k = 3
Output: 20
Note: Sorted: [10,20,30,100,200,300,1000]. Window [10,20,30] has gap 30−10 = 20, the smallest of any width-3 window.

Example 2

Input: arr = [1, 2, 3, 4, 10, 20, 30, 40, 100, 200], k = 4
Output: 3
Note: Sorted already. Window [1,2,3,4] gives 4−1 = 3, beating every other width-4 window.

Example 3

Input: arr = [1, 2, 1, 2, 1], k = 2
Output: 0
Note: Sorted: [1,1,1,2,2]. Window [1,1] gives gap 0 — equal values make unfairness vanish.

Constraints

2 ≤ n ≤ 10⁵ (length of arr)
2 ≤ k ≤ n
0 ≤ arr[i] ≤ 10⁹
Elements may repeat

Clarifying questions4First question: Does unfairness depend on anything besides the min and max of the chosen set?Explore questions

Q1.Does unfairness depend on anything besides the min and max of the chosen set?
No — it's exactly max − min. The middle values are irrelevant, which is the key simplification.
Q2.Do the chosen elements need to keep their original positions?
No. We choose a subset by value, so we're free to sort the array first.
Q3.Can elements repeat, and could the answer be 0?
Yes. If k equal values exist, the window gap is 0 — the minimum possible unfairness.
Q4.Is k guaranteed to be at most n?
Yes, 2 ≤ k ≤ n, so at least one window of size k always exists.

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 realise the chosen numbers must be contiguous after sorting — that the middle elements are irrelevant and only the window endpoints drive the cost.

Where candidates slip

Trying to cleverly pick non-adjacent numbers, or comparing every pair O(n²) instead of seeing that sorting reduces it to k-width windows.

How to stand out

Prove contiguity: if the optimal set skipped a sorted element lying between its min and max, swapping that element in never widens the gap — so a contiguous window is always at least as good.

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 — Check Every k-Subset	`O(C(n,k) · k)`	`O(k)`	Mention it to expose the combinatorial blow-up, then use the 'contiguous after sorting' insight to kill it.	Read
2	Sort + Sliding Window of Size k (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'after sorting, the best k are contiguous, so slide a width-k window'.	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 — Check Every k-Subset

TimeO(C(n,k) · k)SpaceO(k)

Mention it to expose the combinatorial blow-up, then use the 'contiguous after sorting' insight to kill it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The unfairness of a set is just its max minus its min. How many ways are there to choose k of the n numbers?

2Hint 2Explore hint

Enumerate every k-element subset, compute its max − min, and keep the smallest. Correct, but the number of subsets is C(n, k), which explodes.

3Hint 3Explore hint

Before optimising, ask: does the choice of the k−2 middle elements ever affect the score? If not, can you avoid trying every combination?

A · Core idea

The literal reading: enumerate every subset of exactly k elements, compute max − min for each, and remember the smallest.

B · Visual dry run

Interactive dry run

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

arr = [1, 4, 7, 2], k = 2

{1,4}

4 − 1 = 3

Statebest = 3

Final result1

C · Code with teaching comments

solution.javaJava

Brute Force — Check Every k-Subset — reference

2 teaching notes

1
public int maxMin(int k, int[] arr) {
2
    int n = arr.length;
3
    int best = Integer.MAX_VALUE;
4
    int[] combo = new int[k];
5
    best = combine(arr, k, 0, 0, combo, best);
6
    return best;
7
}
8
 
9
private int combine(int[] arr, int k, int start, int depth, int[] combo, int best) {
10
    // A full k-element combination is built — score it by max − min.
11
    if (depth == k) {
12
        int mn = combo[0], mx = combo[0];
13
        for (int v : combo) { mn = Math.min(mn, v); mx = Math.max(mx, v); }
14
        return Math.min(best, mx - mn);
15
    }
16
    for (int i = start; i < arr.length; i++) {
17
        combo[depth] = arr[i];
18
        // Recurse choosing the next element after i, so each subset is generated once.
19
        best = combine(arr, k, i + 1, depth + 1, combo, best);
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(C(n,k) · k) timeO(k) spaceOpen the invariant and proofExplore the proof

ComplexityO(C(n,k) · k) time, O(k) space — There are C(n, k) subsets, and scanning each for its min and max costs O(k). For moderate n and k this is astronomically large.

E · Edge cases and pitfalls3Generating ordered tuples instead of combinations — multiplies the work by k! for no benefit.Explore edge cases

Pitfalls

Generating ordered tuples instead of combinations — multiplies the work by k! for no benefit.
Believing it's viable for large n — C(n,k) is far beyond brute-forceable.
Recomputing min/max from scratch per subset when you could prune — still exponential overall.

03.2

Approach 2 of 2 · Optimal

Sort + Sliding Window of Size k (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'after sorting, the best k are contiguous, so slide a width-k window'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Unfairness only sees the min and max of your pick. If you sort the array, where would a tightly packed group of k numbers live?

2Hint 2Explore hint

Sort ascending. Any contiguous block of k sorted values has its min at the left end and its max at the right end, so its spread is just `arr[i + k - 1] − arr[i]`.

3Hint 3Explore hint

Slide that window across all valid start indices i (from 0 to n − k) and keep the smallest endpoint gap. One pass after the sort.

A · Core idea

B · Visual dry run

Interactive dry run

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

arr = [10, 100, 300, 200, 1000, 20, 30], k = 3

Array state

i=0

[10,20,30] → gap 20 (best)

lo ↓

[0]

[1]

hi ↓

[2]

100

[3]

200

[4]

300

[5]

1000

[6]

Current pointerResolved stateNot processed

Final result20

C · Code with teaching comments

solution.javaJava

Sort + Sliding Window of Size k (Optimal) — optimal

3 teaching notes

1
public int maxMin(int k, int[] arr) {
2
    // Sorting is what makes the optimal k contiguous — the whole method depends on it.
3
    Arrays.sort(arr);
4
    int best = Integer.MAX_VALUE;
5
    // i + k − 1 is the window's right end; the condition keeps it in bounds, including
6
    // the last window.
7
    for (int i = 0; i + k - 1 < arr.length; i++) {
8
        // Spread of a sorted window is last minus first — no inner scan needed.
9
        best = Math.min(best, arr[i + k - 1] - arr[i]);
10
    }
11
    return best;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 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 window slide visits each start index once, O(n − k) = O(n), using a couple of scalars → O(1) extra space.

E · Edge cases and pitfalls6arr = [1, 2, 1, 2, 1], k = 2 — Sorted [1,1,1,2,2]; window [1,1] yields gap 0 — the minimum possible.Explore edge cases

Edge cases handled

arr = [1, 2, 1, 2, 1], k = 2Sorted [1,1,1,2,2]; window [1,1] yields gap 0 — the minimum possible.
k = nOnly one window (the whole sorted array); answer is arr[n−1] − arr[0].
all equal valuesEvery window gap is 0, so the answer is 0.

Pitfalls

Forgetting to sort — window gaps on an unsorted array are meaningless.
Looping i to n − k exclusive — drops the final window and can miss the true minimum.
Scanning each window for min/max — unnecessary; the endpoints already are the extremes.

Practice

Try the solution yourself

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

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.

Off-by-one on the window bound

The last valid window starts at n − k. Looping i < n − k (exclusive) skips it, and the global minimum can live in that final window.

Explore the code comparison

Don't write this

for (int i = 0; i < arr.length - k; i++) {
    best = Math.min(best, arr[i + k - 1] - arr[i]);
}

Write this instead

for (int i = 0; i + k - 1 < arr.length; i++) {
    best = Math.min(best, arr[i + k - 1] - arr[i]);
}

Forgetting to sort

Contiguity only implies closeness in value after sorting. On the raw array, adjacent positions can hold wildly different numbers, so window gaps are nonsense.

Explore the code comparison

Don't write this

return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Write this instead

arr.sort()
return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Taking the gap as a fixed pair instead of sliding

Comparing only the first and last of the whole sorted array ignores tighter interior windows — you must slide across all start indices.

Explore the code comparison

Don't write this

arr.sort()
return arr[k - 1] - arr[0]

Write this instead

arr.sort()
return min(arr[i + k - 1] - arr[i] for i in range(len(arr) - k + 1))

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort + fixed-size sliding window minimising the endpoints' gap

Code pattern to memorize

sort(arr)
best = ∞
for i in 0 .. n-k:
    best = min(best, arr[i + k - 1] - arr[i])
return best

Rules to remember

1Unfairness depends only on the chosen set's min and max — the k−2 middle values don't matter, so cluster them tightly.
2After sorting, the optimal k numbers are always contiguous — never skip elements to build the set.
3The window's gap is just arr[i + k - 1] − arr[i] (last minus first), since the slice is sorted.
4Loop i from 0 to n − k inclusive — off-by-one here drops the last valid window.
5Sort first or none of this holds — the contiguity argument is purely a property of sorted order.

Use this pattern when

Choose a subset of fixed size k to minimise (or bound) the spread between its extremes
The objective depends only on the min and max of the chosen elements
Elements can be freely reordered (no positional constraint)
You can afford an O(n log n) sort

Choose another pattern when

The objective depends on the actual middle values (sum, variance) → not just endpoints, rethink
You must keep original positions / contiguity in the input array → can't sort
k is not fixed (choose any size) → different problem entirely
You need the actual subset, not just the spread → still works, track the window index

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

Minimum Absolute Difference in an Array
Coming soon
Special case with window size 2 — sort and scan adjacent pairs.
Mark and Toys
Another sort-then-prefix greedy, here maximising count under a budget.
Maximize Distance to Closest Person
Coming soon
Scan gaps after fixing positions — gap-minimising/maximising cousin.
Smallest Range Covering K Lists
Coming soon
Generalises window-min-spread to k separate sorted lists with a heap.

Same pattern

←

Mark and Toys

Continue · Next problem

Activity Selection