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 <= 104After 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place.
| 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. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 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