LeetCode Problem 910

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting

Solution

LeetCode 910, Smallest Range II

Problem Understanding

The problem gives us an integer array nums and an integer k. For every element in the array, we must choose exactly one of two operations:

• add k
• subtract k

After modifying every element, we calculate the score of the array, which is defined as:

max(nums) - min(nums)

Our goal is to minimize this score.

The important detail is that every element must be changed independently. One number may increase while another decreases. We are free to choose whichever operation helps minimize the final range.

For example, if:

nums = [0, 10], k = 2

we can transform the array into:

[2, 8]

The range becomes:

8 - 2 = 6

which is smaller than the original range of 10.

The constraints are:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^4
• 0 <= k <= 10^4

These constraints are large enough that exponential or brute force exploration of all possibilities is impossible. Since every element has two choices, there are 2^n possible transformed arrays. Even for moderate values of n, that becomes computationally infeasible.

The constraints strongly suggest that we need a greedy or sorting-based optimization.

Several edge cases are important:

• Arrays with only one element always produce a score of 0
• k = 0 means no effective changes occur
• Already tightly clustered arrays may not benefit from modifications
• Large gaps between adjacent sorted values are important decision points
• Duplicate values must be handled correctly

Approaches

Brute Force Approach

The brute force strategy is to try every possible combination of adding or subtracting k.

For each element:

• choose +k
• or choose -k

Then compute the resulting array's maximum and minimum values, and track the smallest range found.

This works because it exhaustively checks every valid transformed array, guaranteeing the optimal answer.

However, the number of possibilities is:

2^n

For n = 10^4, this is completely impractical.

Even a recursive backtracking solution becomes unusable very quickly.

Key Insight for the Optimal Solution

The critical observation comes from sorting the array.

Suppose the array is sorted:

a0 <= a1 <= a2 <= ... <= an-1

If we decide that:

• elements on the left side get increased by k
• elements on the right side get decreased by k

then the transformed values remain relatively compact.

The optimal solution can always be represented by a partition point:

[ increase ] [ decrease ]

After sorting, we only need to test every possible split between adjacent elements.

For a split at index i:

• elements 0..i become nums[j] + k
• elements i+1..n-1 become nums[j] - k

Then we compute the resulting minimum and maximum values.

This reduces the problem from exponential complexity to a simple linear scan after sorting.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Tries every possible add/subtract combination
Optimal	O(n log n)	O(1) or O(log n)	Sorts array and checks all partition points

Algorithm Walkthrough

1. Sort the array in non-decreasing order.

Sorting is essential because it allows us to reason about the smallest and largest values after modification. Once sorted, we can systematically consider where the transition from +k to -k occurs. 2. Initialize the answer with the original range.

Before making any changes:

answer = nums[n-1] - nums[0]

This serves as the baseline result. 3. Iterate through every possible partition point.

For each index i from 0 to n-2:

• elements 0..i are increased by k
• elements i+1..n-1 are decreased by k

4. Compute the new maximum value.

The largest transformed value can only come from:

• the largest left-side element after increasing:

nums[i] + k

• or the original largest element after decreasing:

nums[n-1] - k

So:

high = max(nums[i] + k, nums[n-1] - k)

5. Compute the new minimum value.

The smallest transformed value can only come from:

• the original smallest element after increasing:

nums[0] + k

• or the first right-side element after decreasing:

nums[i+1] - k

So:

low = min(nums[0] + k, nums[i+1] - k)

6. Update the answer.

The current transformed range is:

high - low

Update the minimum answer accordingly. 7. Return the smallest range found.

Why it works

After sorting, any optimal arrangement can be viewed as a boundary where elements before the boundary are increased and elements after the boundary are decreased.

If two elements violate this ordering, swapping their operations cannot increase the range. Therefore, checking all partition points is sufficient to explore every meaningful configuration.

Because we evaluate every possible boundary, the algorithm is guaranteed to find the minimum achievable score.

Python Solution

from typing import List

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        n = len(nums)

        if n == 1:
            return 0

        nums.sort()

        answer = 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)

            answer = min(answer, high - low)

        return answer

The implementation begins by handling the simplest edge case. If the array contains only one element, the range is always zero regardless of k.

Next, the array is sorted so that we can reason about contiguous partitions. The initial answer is set to the original range before modifications.

The loop examines every possible split position. At each iteration:

• the left portion is treated as increased by k
• the right portion is treated as decreased by k

The possible maximum and minimum transformed values are computed using only the boundary elements. Because the array is sorted, no internal element can exceed these extremes.

Finally, the smallest observed range is returned.

Go Solution

package main

import "sort"

func smallestRangeII(nums []int, k int) int {
	n := len(nums)

	if n == 1 {
		return 0
	}

	sort.Ints(nums)

	answer := nums[n-1] - nums[0]

	for i := 0; i < n-1; i++ {
		high := max(nums[i]+k, nums[n-1]-k)
		low := min(nums[0]+k, nums[i+1]-k)

		answer = min(answer, high-low)
	}

	return answer
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version.

A few Go-specific details are worth noting:

• Go does not provide built-in min and max functions for integers, so helper functions are implemented manually.
• sort.Ints(nums) is used for in-place sorting.
• Integer overflow is not a concern because the constraints are small relative to Go's integer range.
• Slices are modified directly, which is efficient and avoids unnecessary copying.

Worked Examples

Example 1

Input:

nums = [1], k = 0

Sorted array:

[1]

Since there is only one element:

max - min = 1 - 1 = 0

Answer:

0

Example 2

Input:

nums = [0, 10], k = 2

Sorted array:

[0, 10]

Initial range:

10 - 0 = 10

We test the only partition point.

i	Left Side	Right Side	high	low	Range
0	[0+2]	[10-2]	8	2	6

Minimum range:

6

Example 3

Input:

nums = [1, 3, 6], k = 3

Sorted array:

[1, 3, 6]

Initial range:

6 - 1 = 5

Partition at i = 0

Increase left:

1 + 3 = 4

Decrease right:

3 - 3 = 0
6 - 3 = 3

high	low	range
4	0	4

Partition at i = 1

Increase left:

1 + 3 = 4
3 + 3 = 6

Decrease right:

6 - 3 = 3

high	low	range
6	3	3

Minimum range:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation

The algorithm first sorts the array, which requires O(n log n) time. After sorting, we perform a single linear scan across all partition points, which costs O(n).

The additional memory usage is minimal because the algorithm only stores a few variables. The exact auxiliary space depends on the language's sorting implementation.

Test Cases

from typing import List

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        n = len(nums)

        if n == 1:
            return 0

        nums.sort()

        answer = 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)

            answer = min(answer, high - low)

        return answer

solution = Solution()

assert solution.smallestRangeII([1], 0) == 0  # single element
assert solution.smallestRangeII([0, 10], 2) == 6  # example case
assert solution.smallestRangeII([1, 3, 6], 3) == 3  # example case
assert solution.smallestRangeII([1, 2, 3], 0) == 2  # k is zero
assert solution.smallestRangeII([7, 7, 7], 5) == 0  # all elements equal
assert solution.smallestRangeII([1, 10], 100) == 9  # very large k
assert solution.smallestRangeII([1, 4, 7, 10], 2) == 5  # balanced partition
assert solution.smallestRangeII([2, 6, 3, 4, 7, 2, 10, 3, 2, 1], 5) == 7  # mixed values
assert solution.smallestRangeII([0, 0, 0, 10], 2) == 6  # duplicates with outlier
assert solution.smallestRangeII([1, 10000], 10000) == 9999  # constraint boundary

Test Case Summary

Test	Why
[1], k=0	Validates single-element handling
[0,10], k=2	Basic example from problem
[1,3,6], k=3	Demonstrates optimal partitioning
[1,2,3], k=0	Ensures no-op modification works
[7,7,7], k=5	Tests identical elements
[1,10], k=100	Large k compared to values
[1,4,7,10], k=2	Standard sorted partition behavior
Mixed unsorted array	Verifies sorting and greedy logic
[0,0,0,10], k=2	Handles duplicates and outlier
[1,10000], k=10000	Tests upper constraint values

Edge Cases

Single Element Array

When the array contains only one number, the maximum and minimum values are always identical after modification. Even if we add or subtract k, there is still only one element.

A naive implementation might still attempt partition logic and accidentally access invalid indices. The implementation avoids this by returning 0 immediately.

k = 0

When k is zero, every element remains unchanged regardless of whether we choose addition or subtraction.

This case is important because some implementations incorrectly assume modifications always change the values. The algorithm handles this naturally because:

nums[i] + 0 == nums[i] - 0

The computed answer simply becomes the original range.

Large Gaps Between Adjacent Elements

The optimal partition often occurs near large gaps in the sorted array.

For example:

nums = [1, 2, 3, 100]

A naive local strategy might fail to identify the best split. The algorithm correctly evaluates every partition boundary, ensuring that large discontinuities are fully considered.

Duplicate Values

Arrays containing many duplicate values can expose mistakes in min/max calculations.

For example:

nums = [5, 5, 5, 5]

No matter how values are modified, the range can remain very small or even zero.

Because the algorithm relies only on sorted boundary values, duplicates are handled correctly without requiring special logic.