Skip to content

910. Smallest Range II

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 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) {
    ranges::sort(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 mn = min(left, nums[i + 1] - k);
      const int mx = max(right, nums[i] + k);
      ans = min(ans, mx - mn);
    }

    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 mn = Math.min(left, nums[i + 1] - k);
      final int mx = Math.max(right, nums[i] + k);
      ans = Math.min(ans, mx - mn);
    }

    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):
      mn = min(left, b - k)
      mx = max(right, a + k)
      ans = min(ans, mx - mn)

    return ans