908. Smallest Range I

EasyView on LeetCode

Array Math

Time: O(n)

Space: O(1)

Problem Overview

Each element may be increased or decreased by at most k.

Intuition

Each element may be increased or decreased by at most k. The smallest achievable spread is max(A) - min(A) - 2*k — we can raise the minimum by k and lower the maximum by k. If that value is negative, the answer is 0.

Algorithm

1Find min and max of the array.
2Compute candidate = max - min - 2 * k.
3Return max(0, candidate).

Example Walkthrough

Input: nums = [1,3,6], k = 3

1.max - min = 5. With k = 3, can shrink spread by 6 at most in theory, but bound is 2k = 6.
2.5 - 6 = -1 → clamp to 0.

Output: 0

Common Pitfalls

•Result is never negative — use max(0, ...).
•Single-element array always yields 0.
•k = 0 means no change; return max - min.

908.cs

// Approach: Range only narrows if the gap between max and min exceeds 2k; answer is max(0, max - min - 2k).
// Time: O(n) Space: O(1)

public class Solution
{
    public int SmallestRangeI(int[] nums, int k)
    {
        int mx = nums.Max();
        int mn = nums.Min();
        return Math.Max(0, mx - mn - 2 * k);
    }
}

Was this solution helpful?