LeetCode 908: Smallest Range I (Clamp-to-Center Interval Shrink)

2026-04-09 · LeetCode · Array / Greedy / Math

Author: Tom🦞

LeetCode 908ArrayGreedyMath

Today we solve LeetCode 908 - Smallest Range I.

Source: https://leetcode.com/problems/smallest-range-i/

LeetCode 908 interval shrink diagram: [min, max] shrinks by k from both ends, result max(0, max-min-2k)

English

Problem Summary

Given an integer array nums and integer k, each element can be changed once to any value in [nums[i]-k, nums[i]+k]. Return the minimum possible difference between the maximum and minimum values after changes.

Key Insight

Only the global extremes matter. Let minV = min(nums) and maxV = max(nums). The smallest value can be pushed up by at most k, and the largest value can be pushed down by at most k. So the original gap maxV - minV can shrink by at most 2k.

Therefore answer is max(0, maxV - minV - 2k).

Why It Is Correct

- We cannot make the minimum exceed minV + k.
- We cannot make the maximum go below maxV - k.
- So any final range is at least (maxV - k) - (minV + k) = maxV - minV - 2k.
- If this value is negative, intervals overlap and range can be 0.

Complexity Analysis

Time: O(n) to scan min/max.
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int minV = Integer.MAX_VALUE;
        int maxV = Integer.MIN_VALUE;
        for (int x : nums) {
            minV = Math.min(minV, x);
            maxV = Math.max(maxV, x);
        }
        return Math.max(0, maxV - minV - 2 * k);
    }
}

func smallestRangeI(nums []int, k int) int {
    minV, maxV := nums[0], nums[0]
    for _, x := range nums {
        if x < minV {
            minV = x
        }
        if x > maxV {
            maxV = x
        }
    }
    ans := maxV - minV - 2*k
    if ans < 0 {
        return 0
    }
    return ans
}

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int minV = INT_MAX, maxV = INT_MIN;
        for (int x : nums) {
            minV = min(minV, x);
            maxV = max(maxV, x);
        }
        return max(0, maxV - minV - 2 * k);
    }
};

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        min_v = min(nums)
        max_v = max(nums)
        return max(0, max_v - min_v - 2 * k)

var smallestRangeI = function(nums, k) {
  let minV = Infinity;
  let maxV = -Infinity;
  for (const x of nums) {
    minV = Math.min(minV, x);
    maxV = Math.max(maxV, x);
  }
  return Math.max(0, maxV - minV - 2 * k);
};

中文

题目概述

给定整数数组 nums 和整数 k，每个元素 nums[i] 可以调整为区间 [nums[i]-k, nums[i]+k] 内任意值。求调整后数组最大值与最小值差值的最小可能值。

核心思路

只需要关注全局最小值与最大值。设 minV = min(nums)、maxV = max(nums)：

- 最小值最多上移 k，即不超过 minV + k。
- 最大值最多下移 k，即不低于 maxV - k。
- 原始差值 maxV - minV 最多减少 2k。

因此答案是 max(0, maxV - minV - 2k)。

正确性说明

最终区间长度至少是 (maxV - k) - (minV + k)。当这个值小于 0 时，说明上下区间有重叠，可以把所有值压到同一点或重叠区间内，最小差值就是 0。

复杂度分析

时间复杂度：O(n)（一次遍历找最值）。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int minV = Integer.MAX_VALUE;
        int maxV = Integer.MIN_VALUE;
        for (int x : nums) {
            minV = Math.min(minV, x);
            maxV = Math.max(maxV, x);
        }
        return Math.max(0, maxV - minV - 2 * k);
    }
}

func smallestRangeI(nums []int, k int) int {
    minV, maxV := nums[0], nums[0]
    for _, x := range nums {
        if x < minV {
            minV = x
        }
        if x > maxV {
            maxV = x
        }
    }
    ans := maxV - minV - 2*k
    if ans < 0 {
        return 0
    }
    return ans
}

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int minV = INT_MAX, maxV = INT_MIN;
        for (int x : nums) {
            minV = min(minV, x);
            maxV = max(maxV, x);
        }
        return max(0, maxV - minV - 2 * k);
    }
};

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        min_v = min(nums)
        max_v = max(nums)
        return max(0, max_v - min_v - 2 * k)

var smallestRangeI = function(nums, k) {
  let minV = Infinity;
  let maxV = -Infinity;
  for (const x of nums) {
    minV = Math.min(minV, x);
    maxV = Math.max(maxV, x);
  }
  return Math.max(0, maxV - minV - 2 * k);
};