An interesting problem leetcode 910. Smallest Range II
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.
simple C++ solution with explanation - LeetCode Discuss
Last Edit: October 21, 2018 5:01 PM 4.7K VIEWS Sort the vector. Assuming there is a point, on the left of the point…
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
pointis between two numbers).
- Cause there are two segments
(A+K, A+K, ..., A[i]+K, A[i+1]-K, ..., A[n]-K), the first one is on the left of the current
A[i] + Kis the last element of the first segment), the second one is on the right of the current
A[i + 1] - Kis 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] - Kis the smallest element, the largest is
right. Thus, for each point, the largest element should be either
A[i] + Kor
right, the smallest element should be either
A[i + 1] - K.”
Here is my contribution by provding a Python code:
def smallestRangeII(self, A: List[int], K: int) -> int:
if len(A) == 1:return 0
res = A[-1] - A
for i in range(len(A)-1):
this_max = max(A[i]+K, A[-1]-K)
this_min = min(A+K, A[i+1]-K)
res = min(res, this_max - this_min)
Complexity is the sort part which is O(nlogn)