You are given an integer array nums and an integer k.
For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.
The score of nums is the difference between the maximum and minimum elements in nums.
Return the minimum score of nums after changing the values at each index.
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: 3 Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1040 <= k <= 104Problem Overview: You are given an integer array where each element can either increase by K or decrease by K. After applying this change exactly once to every element, the goal is to minimize the difference between the maximum and minimum values in the final array.
The brute force idea is to try every possible combination of adding or subtracting K, but that leads to 2^n possibilities and becomes infeasible quickly. The key observation is that once the array is sorted, the optimal solution always forms a clear boundary: numbers on the left increase by K, and numbers on the right decrease by K. This insight reduces the search space dramatically.
Approach 1: Sorting and Checking Potential Breakpoints (O(n log n) time, O(1) space)
Sort the array first. After sorting, consider a breakpoint between indices i and i+1. All elements from 0..i are increased by K, and all elements from i+1..n-1 are decreased by K. For each breakpoint, compute the new minimum and maximum values. The new maximum is the larger of nums[i] + K and nums[n-1] - K. The new minimum is the smaller of nums[0] + K and nums[i+1] - K. Iterate through every possible breakpoint and keep the smallest range. Sorting costs O(n log n), while the single pass evaluation is O(n). This method relies on a classic greedy observation that only boundary transitions matter.
Approach 2: Direct Calculation of Extremes after Sorting (O(n log n) time, O(1) space)
This approach simplifies the same greedy idea by focusing directly on how the extreme values change after modification. Start with the original range nums[n-1] - nums[0]. After sorting, assume the smallest values will increase by K and the largest values will decrease by K. Scan the array once and evaluate candidate ranges using the adjusted extremes: high = max(nums[n-1] - K, nums[i] + K) and low = min(nums[0] + K, nums[i+1] - K). Update the minimum range across all splits. The reasoning comes from how array ordering limits which elements can become the new extremes.
Recommended for interviews: Interviewers expect the greedy + sorting solution. Start by explaining the brute force intuition to show you understand the full search space, then pivot to the key observation: once sorted, the optimal configuration always splits the array into two groups. Implementing the breakpoint scan in O(n) after sorting demonstrates strong algorithmic reasoning and familiarity with greedy boundary problems.
After sorting the array, our potential strategy is to focus on bridging the maximum and minimum gap by controlling possible breakpoints where the boundary conditions for minimum and maximum flip due to the presorted state.
The algorithm first sorts the input array, then calculates the initial difference between the maximum and minimum. It iterates over the array proposing the change boundary at each index, calculating potential new high and low values (by adjusting ends with ±k), and preserving the minimal difference found.
Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) if we ignore input space.
A slight variation that considers minimizing and maximizing simultaneously, with the goal of finding directly altered extremes without sequence traversals.
With sorted nums, this approach focuses on defining logical min/max around increments/decrements that have the smallest scope impact, using the basic alternative end transforms.
Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place.
According to the problem requirements, we need to find the minimum difference between the maximum and minimum values in the array. Each element can be increased or decreased by k, so we can divide the elements in the array into two parts, one part increased by k and the other part decreased by k. Therefore, we should decrease the larger values in the array by k and increase the smaller values by k to ensure the minimum difference between the maximum and minimum values.
Therefore, we can first sort the array, then enumerate each element in the array, divide it into two parts, one part increased by k and the other part decreased by k, and calculate the difference between the maximum and minimum values. Finally, take the minimum value among all differences.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Checking Potential Breakpoints | Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) if we ignore input space. |
| Direct Calculation of Extremes after Sorting | Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place. |
| Greedy + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Checking Potential Breakpoints | O(n log n) | O(1) | Standard greedy solution when you want to explicitly evaluate each possible split after sorting |
| Direct Calculation of Extremes after Sorting | O(n log n) | O(1) | Cleaner implementation when you directly compute adjusted min/max values while scanning the sorted array |
Smallest Range II | Live Coding with Explanation | Leetcode #910 • Algorithms Made Easy • 7,677 views views
Watch 9 more video solutions →Practice Smallest Range II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor