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.
This approach leverages the concept that if we can adjust elements of the array within the range [-k, k], the maximum score will be the difference between (max(nums) - k) and (min(nums) + k). If this difference is negative or zero, the minimum score is 0, reflecting perfect minimizing of the range.
We can calculate the adjusted minimum possible score directly without iterating over the array repeatedly.
The code first determines the current minimum and maximum in the array. It then computes the potential adjusted score by subtracting 2 * k from the difference between the maximum and minimum. If this resulting score is negative, the answer is 0 because we can perfectly equalize the values with adjustments. Otherwise, it returns the calculated score.
Time Complexity: O(n), where n is the length of the array, as we are scanning through the array to find the min and max.
Space Complexity: O(1), as we are using a constant amount of extra space.
Another method includes simulating each possible adjustment operation, iterating each possibility within [-k, k] for each index. Though practically inefficient for large inputs, it demonstrates comprehension of adjustments and their effects.
This brute force version simulates every possible permutation of adjustments for each index within the allowable range [-k, k]. For each complete permutation, it computes the resultant score and tracks the minimum found across all permutations. Though conceptually straightforward, it is inefficient (O(n * 2^(n * k))) for large n.
Time Complexity: O(n * 2^(n * k)), impractical for large n due to exponential growth.
Space Complexity: O(n) for storing adjustments.
According to the problem description, we can subtract k from the maximum value in the array and add k to the minimum value in the array, which can reduce the difference between the maximum and minimum values in the array.
Therefore, the final answer is the larger value between max(nums) - min(nums) - 2 times k and 0.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Adjusting Max and Min | Time Complexity: O(n), where n is the length of the array, as we are scanning through the array to find the min and max. |
| Brute Force Adjustment Simulation | Time Complexity: O(n * 2^(n * k)), impractical for large n due to exponential growth. |
| Mathematics | — |
| 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 |
LeetCode Smallest Range I Solution Explained - Java • Nick White • 8,177 views views
Watch 9 more video solutions →Practice Smallest Range I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor