Skip to content

910. Smallest Range II

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int smallestRangeII(vector<int>& nums, int k) {
    sort(begin(nums), end(nums));

    int ans = nums.back() - nums.front();
    const int left = nums.front() + k;
    const int right = nums.back() - k;

    for (int i = 0; i + 1 < nums.size(); ++i) {
      const int mini = min(left, nums[i + 1] - k);
      const int maxi = max(right, nums[i] + k);
      ans = min(ans, maxi - mini);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int smallestRangeII(int[] nums, int k) {
    Arrays.sort(nums);

    int ans = nums[nums.length - 1] - nums[0];
    final int left = nums[0] + k;
    final int right = nums[nums.length - 1] - k;

    for (int i = 0; i + 1 < nums.length; ++i) {
      final int min = Math.min(left, nums[i + 1] - k);
      final int max = Math.max(right, nums[i] + k);
      ans = Math.min(ans, max - min);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def smallestRangeII(self, nums: List[int], k: int) -> int:
    nums.sort()

    ans = nums[-1] - nums[0]
    left = nums[0] + k
    right = nums[-1] - k

    for a, b in itertools.pairwise(nums):
      mini = min(left, b - k)
      maxi = max(right, a + k)
      ans = min(ans, maxi - mini)

    return ans