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.
A much more efficient approach involves sorting the array first. The key insight is that to minimize the range (max - min), we should try to increase the smaller numbers and decrease the larger numbers. After sorting, any optimal solution will involve adding k to a prefix of the array and subtracting k from the remaining suffix.
Algorithm
-
- Get the length of the array,
n. Ifn <= 1, return 0. * 2. Sort the arraynumsin non-decreasing order. * 3. Initialize a variableminScorewith the initial rangenums[n-1] - nums[0]. * 4. Iterate with an indexifrom0ton-2. Thisirepresents the last index of the prefix that gets+k. * 5. Inside the loop, for eachi: * a. Calculate the potential maximum of the new array:high = max(nums[i] + k, nums[n-1] - k). * b. Calculate the potential minimum of the new array:low = min(nums[0] + k, nums[i+1] - k). * c. Update the result:minScore = min(minScore, high - low). * 6. After the loop, returnminScore.
- Get the length of the array,
Walkthrough
Let's sort the input array nums. After sorting, let the elements be nums[0], nums[1], ..., nums[n-1]. The initial score can be nums[n-1] - nums[0]. This corresponds to a scenario where we either add k to all elements or subtract k from all elements, which doesn't change the score. This serves as our initial upper bound for the minimum score. The core idea is that for an optimal arrangement, there must be a split point i such that all elements nums[0]...nums[i] are increased by k, and all elements nums[i+1]...nums[n-1] are decreased by k. This is because if we had nums[j] - k and nums[l] + k for some j < l, we could swap the operations to nums[j] + k and nums[l] - k. This swap would not increase the overall range and might decrease it, suggesting the partitioned structure is optimal. We can iterate through all possible split points i from 0 to n-2. For each split point i, the new maximum element will be max(nums[i] + k, nums[n-1] - k) and the new minimum element will be min(nums[0] + k, nums[i+1] - k). We calculate the score for this split and update our overall minimum score. After checking all possible splits, the minimum score found is the answer. java import java.util.Arrays; class Solution { public int smallestRangeII(int[] nums, int k) { int n = nums.length; if (n <= 1) { return 0; } Arrays.sort(nums); int minScore = nums[n - 1] - nums[0]; for (int i = 0; i < n - 1; i++) { int high = Math.max(nums[i] + k, nums[n - 1] - k); int low = Math.min(nums[0] + k, nums[i + 1] - k); minScore = Math.min(minScore, high - low); } return minScore; } }
Complexity
Time
O(N log N), where N is the number of elements. The sorting step dominates the complexity. The subsequent loop runs N-1 times with constant time operations.
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
Trade-offs
Pros
Highly efficient and passes for the given constraints.
Based on a clever greedy insight that simplifies the problem from exponential to polynomial time.
Cons
Requires sorting, which might not be ideal if the array is frequently updated.
The logic is less intuitive than the brute-force approach and requires a proof of correctness.
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; }}class Solution {public: int smallestRangeII(vector<int> &nums, int k) { sort(nums.begin(), nums.end()); int n = nums.size(); int ans = nums[n - 1] - nums[0]; for (int i = 1; i < n; ++i) { int mi = min(nums[0] + k, nums[i] - k); int mx = max(nums[i - 1] + k, nums[n - 1] - k); ans = min(ans, mx - mi); } return ans; }};class Solution: def smallestRangeII(self, nums: List[int], k: int) -> int: nums . sort() ans = nums[- 1] - nums[0] for i in range(1, len(nums)): mi = min(nums[0] + k, nums[i] - k) mx = max(nums[i - 1] + k, nums[- 1] - k) ans = min(ans, mx - mi) return ansVideo 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.