Smallest Range II

Smallest Range II

What is this problem about?

The "Smallest Range II" interview question is a "MEDIUM" difficulty version of the previous problem. Again, you can add or subtract k from each element. But here, the choice is binary: for each nums[i], you must either do nums[i] + k or nums[i] - k. You want to find the minimum possible range (max - min). This "Smallest Range II coding problem" is much harder because the relative order of elements can change.

Why is this asked in interviews?

Meta and Amazon ask this to test sorting and greedy strategies. It requires you to realize that if you sort the array, there will be a "split point" where all elements to the left are increased by k and all elements to the right are decreased by k. Finding the best split point is the crux of the problem.

Algorithmic pattern used

This follows the "Sorting and Greedy interview pattern".

1. Sort the array nums.
2. Initial range is nums[n-1] - nums[0].
3. For each possible split point i from 0 to n-2:
   • After operations, the potential candidates for the new minimum are nums[0] + k and nums[i+1] - k.
   • The potential candidates for the new maximum are nums[i] + k and nums[n-1] - k.
   • Calculate the range for this split point: max(max_candidates) - min(min_candidates).
4. The answer is the minimum range found across all split points.

Example explanation

Array: [1, 3, 6], k = 3. Sorted: [1, 3, 6].

1. No split: 6 - 1 = 5.
2. Split after 1:
   • Left side (+3): [4]. Right side (-3): [0, 3].
   • New array: [4, 0, 3]. Range: 4 - 0 = 4.
3. Split after 3:
   • Left side (+3): [4, 6]. Right side (-3): [3].
   • New array: [4, 6, 3]. Range: 6 - 3 = 3. Smallest range is 3.

Common mistakes candidates make

The most common mistake is not sorting the array first. Another error is not considering that the original minimum (first element) and original maximum (last element) are always the core of the new min and max after the operations. Many candidates also find the split-point logic counter-intuitive and struggle to identify the four critical values at each step.

Interview preparation tip

Sorting often reveals hidden properties in range and difference problems. Once sorted, you only need to check the boundaries between elements. This "Smallest Range II interview question" is a classic example of using sorting to reduce a complex combinatorial problem into a linear scan.