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>& A, int K) {
    sort(begin(A), end(A));

    int ans = A.back() - A.front();
    int left = A.front() + K;
    int right = A.back() - K;

    for (int i = 0; i + 1 < A.size(); ++i) {
      int min = std::min(left, A[i + 1] - K);
      int max = std::max(right, A[i] + K);
      ans = std::min(ans, max - min);
    }

    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[] A, int K) {
    Arrays.sort(A);

    int ans = A[A.length - 1] - A[0];
    int left = A[0] + K;
    int right = A[A.length - 1] - K;

    for (int i = 0; i + 1 < A.length; ++i) {
      int min = Math.min(left, A[i + 1] - K);
      int max = Math.max(right, A[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, A: List[int], K: int) -> int:
    A.sort()

    ans = A[-1] - A[0]
    left = A[0] + K
    right = A[-1] - K

    for a, b in zip(A, A[1:]):
      mini = min(left, b - K)
      maxi = max(right, a + K)
      ans = min(ans, maxi - mini)

    return ans