problemmediumalgorithmsleetcode-910leetcode 910leetcode910

Smallest Range II

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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

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 <= 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

C++
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;
    }
};
Go
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 }
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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
    }
}
TypeScript
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.

Comments