Smallest Range II: Minimizing the Gap After Adding or Subtracting k

LeetCode 910, Smallest Range II, gives you an integer array nums and an integer k. For each element, you must add either +k or -k (you choose independently per element). After transforming every element, return the minimum possible difference between the largest and smallest values in the modified array.

Why this problem matters

Smallest Range II is a classic example of how sorting transforms a combinatorial explosion into a linear scan. Without sorting, you would face 2^n possible assignments of +k or -k to each element. With sorting, the problem collapses to trying n-1 split points. This "sort then sweep" pattern appears in dozens of array problems where you need to minimize or maximize some range or gap.

The problem also teaches you to think about what stays invariant after transformation. Adding k to small elements and subtracting k from large elements compresses the range. Adding k to large elements and subtracting k from small ones expands it. Once you see this monotonic relationship, the greedy split approach becomes natural.

The brute force approach

The most direct approach: try all 2^n possible sign assignments, compute the range for each, and return the minimum. This is correct but exponential. For n = 10000, you would need to evaluate roughly 10^3000 configurations. That is clearly not going to work.

A slightly better idea: for each pair of elements, decide whether they should both go up, both go down, or go in opposite directions. But this still does not give you a clean structure to exploit.

The key insight

After sorting the array, the optimal strategy always has a specific structure. There exists some split point i such that all elements at indices 0 through i receive +k, and all elements at indices i+1 through n-1 receive -k. Why? Because if a smaller element gets -k while a larger element gets +k, the gap only widens. You always want to boost the small elements and shrink the large ones.

Once you fix a split point i, the transformed array has:

• Elements nums[0]+k, nums[1]+k, ..., nums[i]+k on the left
• Elements nums[i+1]-k, nums[i+2]-k, ..., nums[n-1]-k on the right

The maximum of the transformed array is max(nums[i]+k, nums[n-1]-k). The minimum is min(nums[0]+k, nums[i+1]-k). The range is their difference.

You try every split point from i = 0 to i = n-2, compute the range each time, and keep the minimum. You also consider the case where every element gets the same sign (which gives the original range nums[n-1] - nums[0]).

Walking through it step by step

Let us trace through a small example with nums = [3, 1, 6] and k = 3.

The solution

def smallestRangeII(nums, k):
    nums.sort()
    n = len(nums)
    result = nums[-1] - nums[0]
    for i in range(n - 1):
        high = max(nums[i] + k, nums[-1] - k)
        low = min(nums[0] + k, nums[i + 1] - k)
        result = min(result, high - low)
    return result

The code is concise because the key insight does all the heavy lifting. After sorting, you initialize result with the original range (the case where all elements get the same sign, which cancels out). Then for each split point i, you compute the new maximum and minimum directly from the boundary elements and update the result.

Why do you only need to check boundary elements? After sorting:

• The largest element on the left side of the split is always nums[i] + k (since the array is sorted, index i is the largest on the left)
• The largest element on the right side is always nums[n-1] - k (the last element minus k)
• The smallest on the left is always nums[0] + k (the first element plus k)
• The smallest on the right is always nums[i+1] - k (the first element on the right side minus k)

So the overall maximum is max(nums[i]+k, nums[n-1]-k) and the overall minimum is min(nums[0]+k, nums[i+1]-k).

Complexity analysis

The sorting dominates the time complexity. The subsequent loop is a single linear pass. Space usage depends on whether your language sorts in place. In Python, list.sort() is in-place, so extra space is O(1) beyond the sort's internal overhead.

Building blocks

1. Sorting for structural insight

Sorting reveals the monotonic structure that makes the greedy approach work. Without sorting, you cannot claim that all +k elements should be on the left and all -k elements on the right. This is a recurring theme: when the problem involves ranges, gaps, or extremes, sorting often unlocks a linear-time solution.

2. Boundary element reasoning

After fixing the split, you only need to check four values: the endpoints of each partition. This is because sorting guarantees that within each partition, the extreme values are at the boundaries. You never need to scan the entire partition to find the max or min.

3. Greedy split enumeration

Instead of trying all 2^n binary choices, you reduce to n-1 structured choices. This reduction from exponential to linear is the hallmark of a well-chosen greedy invariant. The key guarantee is that any optimal solution must have this split structure after sorting.

Edge cases

• Single element: When n = 1, the result is always 0. Adding or subtracting k from a single element does not create a range. The loop does not execute, and nums[-1] - nums[0] = 0.
• All elements equal: If every element is the same, the range is 0 regardless of k. Every element gets shifted by the same amount (either all +k or all -k), keeping the range at 0.
• k = 0: When k is 0, adding or subtracting 0 changes nothing. The answer is simply nums[-1] - nums[0].
• Large k relative to the range: When k is much larger than the spread of the array, the split still works. The formula handles this correctly because nums[i]+k will dominate the maximum on the left side.
• Two elements: With just two elements [a, b] where a is smaller or equal to b, the answer is min(b-a, abs((b-k)-(a+k))) which simplifies to min(b-a, abs(b-a-2k)). The general formula captures this.

From understanding to recall

The conceptual leap in Smallest Range II is seeing that sorting converts an exponential search into a linear scan. Once you internalize that insight, the implementation flows naturally. But the details matter: remembering that the new max is max(nums[i]+k, nums[n-1]-k) and the new min is min(nums[0]+k, nums[i+1]-k) requires you to visualize the split structure clearly.

Spaced repetition helps cement the boundary reasoning. After a few review sessions, you will automatically picture the sorted array with a split line, left elements going up, right elements going down, and the four boundary values that determine the range. That mental image is what turns a 20-minute derivation into a 3-minute implementation.

The pattern of "sort, then try all split points" also transfers to problems like minimizing the maximum difference between adjacent elements or partitioning arrays into groups with bounded ranges. Once this template is in your long-term memory, you recognize it instantly when a new problem has that shape.

Related posts

• Maximum Subarray - Another array problem where a single linear scan finds the optimal answer after identifying the right invariant
• Best Time to Buy and Sell Stock - Tracking running min/max values while sweeping through an array to find the optimal range
• Container With Most Water - A two-pointer approach that also reasons about how moving boundaries affects the range

Smallest Range II rewards you for slowing down and thinking about structure before coding. The implementation is five lines. The insight that makes those five lines correct is the entire challenge. Once you see the split structure in sorted order, the rest writes itself.