Smallest Range II — Solution in Python, Java & C++
Smallest Range II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and math.
Smallest Range II is a medium coding problem on arrays, math and sorting, asked in Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Sorting, Greedy
- Asked at: Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums and an integer k. For every index i you must change nums[i] to either nums[i] + k or nums[i] - k (each index chooses independently).
The score of the resulting array is its maximum element minus its minimum element. Return the smallest score you can achieve.
Example 1
Input: nums = [1], k = 0
Output: 0
Example 2
Input: nums = [0,10], k = 2
Output: 6
Explanation: Change to [2,8]: the score is 8 - 2 = 6.
Example 3
Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change to [4,6,3]: the score is 6 - 3 = 3.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 10^40 <= k <= 10^4
Hints for Smallest Range II
Hint 1
Sort the array. Is there an optimal choice where the smaller values all go up and the larger values all go down?
Hint 2
Yes — if some
a < bhadagoing down andbgoing up, swapping their directions never widens the range. So the answer is a split point: the firsti + 1sorted values get+k, the rest get-k.Hint 3
For a split after index
i, the maximum ismax(a[n-1] - k, a[i] + k)and the minimum ismin(a[0] + k, a[i+1] - k). Also consider not splitting at all.
How to solve Smallest Range II
After sorting, some optimal answer adds k to a prefix and subtracts k from the suffix, so only n split points need checking.
Approach
- Sort
numsintoa; the no-split answer (everyone moves the same way) isa[n-1] - a[0]. - For each split after index
i(from 0 to n−2): the candidates for the maximum area[i] + kanda[n-1] - k, and for the minimuma[0] + kanda[i+1] - k. - Track the smallest
max - minover all splits and return it.
Why it works
Take an optimal assignment where some smaller value a goes down while a larger value b goes up. Swapping them (a up, b down) produces values a + k and b - k, which both lie between a - k and b + k, so the minimum does not drop and the maximum does not rise. Repeating the swap yields an optimal assignment shaped as 'prefix up, suffix down'. In that shape the largest value is either the last raised element or the last element lowered, and the smallest is either the first raised element or the first lowered one, which is exactly what each split computes.
Complexity
- Time —
O(n log n) - Space —
O(n) for the sorted copy (O(1) extra if sorting in place)
Pitfalls
- Every element must move — leaving one unchanged is not allowed (that is the variant Smallest Range I relaxes).
- The all-same-direction case (
a[n-1] - a[0]) must be the starting answer; withk = 0it is the answer. - The minimum after a split is not always
a[0] + k: the first lowered elementa[i+1] - kcan be smaller.
Reference solution
Python
from typing import List
def smallestRangeII(nums: List[int], k: int) -> int:
a = sorted(nums)
n = len(a)
best = a[-1] - a[0]
for i in range(n - 1):
high = max(a[-1] - k, a[i] + k)
low = min(a[0] + k, a[i + 1] - k)
best = min(best, high - low)
return bestJava
public static int smallestRangeII(int[] nums, int k) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
int best = a[n - 1] - a[0];
for (int i = 0; i + 1 < n; i++) {
int high = Math.max(a[n - 1] - k, a[i] + k);
int low = Math.min(a[0] + k, a[i + 1] - k);
best = Math.min(best, high - low);
}
return best;
}C++
int smallestRangeII(vector<int>& nums, int k) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = a.size();
int best = a[n - 1] - a[0];
for (int i = 0; i + 1 < n; i++) {
int high = max(a[n - 1] - k, a[i] + k);
int low = min(a[0] + k, a[i + 1] - k);
best = min(best, high - low);
}
return best;
}JavaScript
var smallestRangeII = function(nums, k) {
var a = nums.slice().sort(function(p, q) { return p - q; });
var n = a.length;
var best = a[n - 1] - a[0];
for (var i = 0; i + 1 < n; i++) {
var high = Math.max(a[n - 1] - k, a[i] + k);
var low = Math.min(a[0] + k, a[i + 1] - k);
best = Math.min(best, high - low);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms