Smallest Range I — Solution in Python, Java & C++
Smallest Range I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and math.
Smallest Range I is an easy coding problem on arrays and math, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Math
- Asked at: Amazon, 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 each index you may change nums[i] to any value in the range [nums[i] - k, nums[i] + k], once.
Return the minimum possible difference between the largest and smallest value of the resulting array.
Example 1
Input: nums = [1], k = 0
Output: 0
Example 2
Input: nums = [0,10], k = 2
Output: 6
Explanation: Turn [0,10] into [2,8].
Example 3
Input: nums = [1,3,6], k = 3
Output: 0
Constraints
1 <= nums.length <= 400 <= nums[i] <= 100000 <= k <= 10000
Hints for Smallest Range I
Hint 1
Only the current minimum and maximum matter — everything else can be moved inside whatever gap they leave.
Hint 2
Raise the minimum by
kand lower the maximum byk.Hint 3
If they cross, the whole array can be made equal, so the answer is 0 rather than a negative number.
How to solve Smallest Range I
Only the extremes matter: raise the minimum by k, lower the maximum by k, and clamp at zero.
Approach
- Return
max(0, max(nums) - min(nums) - 2k).
Why it works
Every element can be shifted independently, and any element between the new min and max can be left alone or moved inside; if the shifted extremes cross, everything can be made equal.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Without the clamp the answer goes negative when
2kexceeds the spread.
Reference solution
Python
def smallestRangeI(nums, k: int) -> int:
return max(0, max(nums) - min(nums) - 2 * k)Java
public static int smallestRangeI(int[] nums, int k) {
int lo = nums[0], hi = nums[0];
for (int x : nums) {
lo = Math.min(lo, x);
hi = Math.max(hi, x);
}
return Math.max(0, hi - lo - 2 * k);
}C++
int smallestRangeI(vector<int>& nums, int k) {
int lo = nums[0], hi = nums[0];
for (int x : nums) {
lo = min(lo, x);
hi = max(hi, x);
}
return max(0, hi - lo - 2 * k);
}JavaScript
var smallestRangeI = function(nums, k) {
let lo = nums[0], hi = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] < lo) lo = nums[i];
if (nums[i] > hi) hi = nums[i];
}
const span = hi - lo - 2 * k;
return span > 0 ? span : 0;
};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