Watch 10 video solutions for Smallest Range I, a easy level problem involving Array, Math. This walkthrough by Nick White has 8,177 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums and an integer k.
In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.
The score of nums is the difference between the maximum and minimum elements in nums.
Return the minimum score of nums after applying the mentioned operation at most once for each index in it.
Example 1:
Input: nums = [1], k = 0 Output: 0 Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
Example 2:
Input: nums = [0,10], k = 2 Output: 6 Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
Example 3:
Input: nums = [1,3,6], k = 3 Output: 0 Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1040 <= k <= 104Problem Overview: You are given an integer array and a value k. For every element, you can either add k or subtract k. After performing this operation once on each element, the goal is to minimize the difference between the maximum and minimum values in the array.
Approach 1: Brute Force Adjustment Simulation (O(n²) time, O(1) space)
The brute force idea is to simulate possible adjustments and observe how the minimum and maximum values change. For each element, consider it as a potential minimum after applying +k, and for every other element consider applying -k to see if it becomes the maximum. Iterate over pairs of elements and compute the resulting range after adjustments. This approach explicitly evaluates combinations of adjustments to see which produces the smallest range. While straightforward, it performs redundant comparisons and scales poorly for large arrays because every candidate pair requires recomputing the resulting minimum and maximum.
This method helps build intuition about how adding or subtracting k shifts values toward or away from the center of the distribution. However, the nested iteration results in O(n²) time complexity, making it inefficient when n grows.
Approach 2: Adjusting Max and Min (O(n) time, O(1) space)
The key observation is that every element can move within the range [nums[i] - k, nums[i] + k]. To minimize the final spread, you want to push large values downward and small values upward. The maximum possible reduction happens when the original maximum decreases by k and the original minimum increases by k.
Compute the current minimum and maximum in the array using a single pass. The original range is maxVal - minVal. After adjustment, the best possible range becomes (maxVal - k) - (minVal + k), which simplifies to maxVal - minVal - 2k. If this value becomes negative, the range cannot go below zero, so clamp the result using max(0, maxVal - minVal - 2k). This insight removes the need to simulate every adjustment and reduces the problem to a simple scan.
This approach relies on properties of array traversal and basic math reasoning. Because only the global minimum and maximum matter, the algorithm runs in linear time with constant memory.
Recommended for interviews: Interviewers typically expect the max–min adjustment insight. Demonstrating the brute force reasoning first shows you understand the problem constraints, but quickly deriving the max(0, max - min - 2k) formula signals strong problem-solving and pattern recognition skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Adjustment Simulation | O(n²) | O(1) | Useful for understanding how ±k adjustments affect pairwise min/max values |
| Adjusting Max and Min | O(n) | O(1) | Optimal approach when only the global min and max determine the final range |