Problem

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 minimumscore of _nums after changing the values at each index.

Examples

Example 1

1
2
3

Input: nums = [1], k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2

1
2
3

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

1
2
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 <= 10^4
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4

Solution

Method 1 – Greedy Partition and Sort

Intuition

Sort the array. For each possible partition, increase all elements to the left by k and decrease all elements to the right by k. The answer is the minimum difference between the new max and min over all partitions.

Approach

  1. Sort nums.
  2. For each i from 0 to n-2:
    • Increase nums[0..i] by k, decrease nums[i+1..n-1] by k.
    • The new min is min(nums[0]+k, nums[i+1]-k).
    • The new max is max(nums[i]+k, nums[n-1]-k).
    • Track the minimum difference.
  3. Return the minimum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = nums[n-1] - nums[0];
        for (int i = 0; i < n-1; ++i) {
            int hi = max(nums[i]+k, nums[n-1]-k);
            int lo = min(nums[0]+k, nums[i+1]-k);
            ans = min(ans, hi-lo);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func smallestRangeII(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    ans := nums[n-1] - nums[0]
    for i := 0; i < n-1; i++ {
        hi := max(nums[i]+k, nums[n-1]-k)
        lo := min(nums[0]+k, nums[i+1]-k)
        if hi-lo < ans { ans = hi-lo }
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[n-1] - nums[0];
        for (int i = 0; i < n-1; ++i) {
            int hi = Math.max(nums[i]+k, nums[n-1]-k);
            int lo = Math.min(nums[0]+k, nums[i+1]-k);
            ans = Math.min(ans, hi-lo);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun smallestRangeII(nums: IntArray, k: Int): Int {
        nums.sort()
        var ans = nums.last() - nums.first()
        for (i in 0 until nums.size-1) {
            val hi = maxOf(nums[i]+k, nums.last()-k)
            val lo = minOf(nums.first()+k, nums[i+1]-k)
            ans = minOf(ans, hi-lo)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def smallestRangeII(self, nums: list[int], k: int) -> int:
        nums.sort()
        ans = nums[-1] - nums[0]
        for i in range(len(nums)-1):
            hi = max(nums[i]+k, nums[-1]-k)
            lo = min(nums[0]+k, nums[i+1]-k)
            ans = min(ans, hi-lo)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn smallest_range_ii(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let n = nums.len();
        let mut ans = nums[n-1] - nums[0];
        for i in 0..n-1 {
            let hi = nums[i]+k.max(nums[n-1]-k);
            let lo = nums[0]+k.min(nums[i+1]-k);
            ans = ans.min(hi-lo);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    smallestRangeII(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        let ans = nums[nums.length-1] - nums[0];
        for (let i = 0; i < nums.length-1; ++i) {
            const hi = Math.max(nums[i]+k, nums[nums.length-1]-k);
            const lo = Math.min(nums[0]+k, nums[i+1]-k);
            ans = Math.min(ans, hi-lo);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of nums. Sorting dominates.
  • 🧺 Space complexity: O(1), if sorting in-place, otherwise O(n) for the sort.