Smallest Range II
MedPrompt
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 <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible modification of the array. For each element, we have two choices: add k or subtract k. With n elements, this leads to 2^n possible modified arrays. We generate each one, calculate its score (max - min), and find the minimum score among all possibilities.
Algorithm
-
- Define a recursive function, say
findMinScore(index, modifiedArray). * 2. The base case for the recursion is whenindexreaches the end of the array. * 3. In the base case, calculate the difference between the maximum and minimum elements ofmodifiedArrayand update the global minimum score. * 4. For the recursive step atindex: * a. Make a recursive call for the case where the element atindexisnums[index] + k. * b. Make another recursive call for the case where the element atindexisnums[index] - k. * 5. Initialize the process by calling the function withindex = 0.
- Define a recursive function, say
Walkthrough
The core idea is to use a recursive helper function that builds every possible modified array. The function takes the current index i and a data structure to hold the modified numbers. At each index i, we make two recursive calls: one where nums[i] is changed to nums[i] + k, and another where nums[i] is changed to nums[i] - k. The base case for the recursion is when we have processed all elements (i.e., i == nums.length). At this point, we have a fully modified array. In the base case, we iterate through the modified array to find its maximum and minimum elements, calculate the score, and update a global minimum score variable. This method is exhaustive but computationally very expensive. java class Solution { int minScore = Integer.MAX_VALUE; public int smallestRangeII(int[] nums, int k) { int[] modifiedNums = new int[nums.length]; findMinScore(nums, k, 0, modifiedNums); return minScore; } private void findMinScore(int[] originalNums, int k, int index, int[] modifiedNums) { if (index == originalNums.length) { if (originalNums.length == 0) { minScore = 0; return; } int minVal = modifiedNums[0]; int maxVal = modifiedNums[0]; for (int i = 1; i < modifiedNums.length; i++) { minVal = Math.min(minVal, modifiedNums[i]); maxVal = Math.max(maxVal, modifiedNums[i]); } minScore = Math.min(minScore, maxVal - minVal); return; } modifiedNums[index] = originalNums[index] + k; findMinScore(originalNums, k, index + 1, modifiedNums); modifiedNums[index] = originalNums[index] - k; findMinScore(originalNums, k, index + 1, modifiedNums); } }
Complexity
Time
O(N * 2^N), where N is the number of elements in `nums`. There are `2^N` possible combinations of adding or subtracting `k`. For each combination, we spend O(N) time to find the minimum and maximum values.
Space
O(N), where N is the number of elements in `nums`. This is due to the recursion depth and the space needed to store the modified array for each path.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer by exploring all possibilities.
Cons
Extremely inefficient due to its exponential nature.
Infeasible for the given constraints where
nums.lengthcan be up to 10^4.
Solutions
Solution
class Solution {public int smallestRangeII(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int ans = nums[n - 1] - nums[0]; for (int i = 1; i < n; ++i) { int mi = Math.min(nums[0] + k, nums[i] - k); int mx = Math.max(nums[i - 1] + k, nums[n - 1] - k); ans = Math.min(ans, mx - mi); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.