LeetCode 908: Smallest Range I

Meta Data

#

Difficulty: easy First Attempt: 2022-09-25

• Submissions: Wrong Answer ×5 → Accepted

Approach

#

Only the maximum and minimum matter (Math Template 4): the maximum can drop by k and the minimum rise by k, shrinking the gap by up to 2k; every other value lies between and can follow. The gap cannot go below 0.

My Attempts

#

The first four computed max + min instead of max - min; after fixing that, a gap larger than 2k forgot to subtract 2k: [9, 0], k = 3 should be 3; it returned 9.

Solution

#

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        return max(0, max(nums) - min(nums) - 2 * k)

Complexity

#

Time O(n), space O(1).

Mistakes to Avoid

#

• Take the maximum minus the minimum, then subtract 2k.

Interview Explanation

#

Only the extremes matter: the maximum drops by k and the minimum rises by k, so the gap shrinks by up to 2k but not below 0. Time O(n).