Watch 10 video solutions for Smallest Range II, a medium level problem involving Array, Math, Greedy. This walkthrough by Algorithms Made Easy has 7,677 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.
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.
| 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 |