Problem

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return _the minimumscore of _nums after applying the mentioned operation at most once for each index in it.

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: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4

Solution

Method 1 – Greedy Min/Max Adjustment

Intuition

We can increase each element by up to k or decrease by up to k. The smallest possible range is max(0, max(nums) - min(nums) - 2*k).

Approach

  1. Find the minimum and maximum of nums.
  2. The answer is max(0, max - min - 2*k).

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int mn = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        return max(0, mx - mn - 2*k);
    }
};
1
2
3
4
5
6
7
8
9

func smallestRangeI(nums []int, k int) int {
    mn, mx := nums[0], nums[0]
    for _, v := range nums {
        if v < mn { mn = v }
        if v > mx { mx = v }
    }
    if mx-mn-2*k > 0 { return mx-mn-2*k }
    return 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int mn = nums[0], mx = nums[0];
        for (int v : nums) {
            if (v < mn) mn = v;
            if (v > mx) mx = v;
        }
        return Math.max(0, mx - mn - 2*k);
    }
}
1
2
3
4
5
6
7

class Solution {
    fun smallestRangeI(nums: IntArray, k: Int): Int {
        val mn = nums.minOrNull()!!
        val mx = nums.maxOrNull()!!
        return maxOf(0, mx - mn - 2*k)
    }
}
1
2
3

class Solution:
    def smallestRangeI(self, nums: list[int], k: int) -> int:
        return max(0, max(nums) - min(nums) - 2*k)
1
2
3
4
5
6
7

impl Solution {
    pub fn smallest_range_i(nums: Vec<i32>, k: i32) -> i32 {
        let mn = *nums.iter().min().unwrap();
        let mx = *nums.iter().max().unwrap();
        (mx - mn - 2*k).max(0)
    }
}
1
2
3
4
5
6

class Solution {
    smallestRangeI(nums: number[], k: number): number {
        const mn = Math.min(...nums), mx = Math.max(...nums);
        return Math.max(0, mx - mn - 2*k);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. One pass to find min and max.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.