An interesting problem leetcode 910. Smallest Range II

Jimmy (xiaoke) Shen
2 min readDec 16, 2019


An nice explanation is from the following link. As it is too clear, I will not reinvent the wheel. Credits go to the original author.

All the following is from above link:

  • “Sort the vector.
  • Assuming there is a point, on the left of the point, all elements add K, on the right of the point, all elements subtract K, check each possible point. (a point is between two numbers).
  • Cause there are two segments (A[0]+K, A[1]+K, ..., A[i]+K, A[i+1]-K, ..., A[n]-K), the first one is on the left of the current point (A[i] + K is the last element of the first segment), the second one is on the right of the current point (A[i + 1] - K is the first element of the second segment).
  • For the first segment, the smallest element is left, the largest is A[i] + K; For the second segment, A[i + 1] - K is the smallest element, the largest is right. Thus, for each point, the largest element should be either A[i] + K or right, the smallest element should be either left or A[i + 1] - K.”

Here is my contribution by provding a Python code:

class Solution:
def smallestRangeII(self, A: List[int], K: int) -> int:
if len(A) == 1:return 0
res = A[-1] - A[0]
for i in range(len(A)-1):
this_max = max(A[i]+K, A[-1]-K)
this_min = min(A[0]+K, A[i+1]-K)
res = min(res, this_max - this_min)
return res

Complexity is the sort part which is O(nlogn)



Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi