Difficulty: 🟢 Easy
Topics: Array, Math

Solution

LeetCode 908 - Smallest Range I

Problem Understanding

The problem gives us an integer array nums and an integer k. For every element in the array, we are allowed to modify it once by adding any integer value in the range [-k, k]. In other words, each number can either increase by at most k, decrease by at most k, or remain unchanged.

After performing these operations, we define the score of the array as:

$\text{score} = \max(nums) - \min(nums)$

Our goal is to minimize this score as much as possible.

Restated more intuitively, we want to shrink the gap between the largest and smallest numbers in the array. Since every number can move within a limited range, we should try to move large numbers downward and small numbers upward.

The constraints are relatively small:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^4
0 <= k <= 10^4

These constraints tell us that performance is not extremely demanding, but we should still aim for a clean linear-time solution.

There are several important edge cases to consider:

Arrays with only one element already have a score of 0
When k = 0, no modifications are possible
When the difference between maximum and minimum is less than or equal to 2 * k, the range can be completely eliminated
Arrays with repeated values should still behave correctly
Very large k values may allow all elements to overlap into a common value

The problem guarantees that the array is non-empty, so we never need to handle an empty input.

Approaches

Brute Force Approach

A brute-force solution would attempt to explore all possible adjusted values for every element. Since each number can become any value in the interval:

$[nums[i]-k,\ nums[i]+k]$

we could theoretically try every combination and compute the resulting score.

However, this quickly becomes infeasible. Even for a small array, the number of possible adjusted arrays grows exponentially. If each element has roughly 2k + 1 possible values, the total number of combinations becomes:

$(2k+1)^n$

This is far too slow for the constraints.

The brute-force idea is conceptually correct because it checks every possible final configuration, but it is computationally impractical.

Optimal Observation

The key insight is that only the minimum and maximum elements matter.

Suppose:

minimum = min(nums)
maximum = max(nums)

To minimize the range:

We should increase the minimum as much as possible, which means adding k
We should decrease the maximum as much as possible, which means subtracting k

After adjustment:

$\text{new range} = (\max(nums)-k) - (\min(nums)+k)$

which simplifies to:

$\text{new range} = \max(nums)-\min(nums)-2k$

If this value becomes negative, it means the intervals overlap completely, so the minimum possible score is 0.

Therefore the final answer is:

$\max(0,\ \max(nums)-\min(nums)-2k)$

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((2k+1)^n)	O(n)	Tries every possible modification combination
Optimal	O(n)	O(1)	Uses only the global minimum and maximum

Algorithm Walkthrough

Find the minimum value in the array.

This represents the smallest element that contributes to the score. To reduce the range, we want to move this value upward as much as possible. 2. Find the maximum value in the array.

This represents the largest element in the array. To reduce the range, we want to move this value downward as much as possible. 3. Compute the original range.

The original score is:

$\max(nums)-\min(nums)$ 4. Reduce the range by 2 * k.

Since the minimum can increase by k and the maximum can decrease by k, the total reduction is:

$2k$ 5. Clamp the result to zero.

If the adjusted range becomes negative, it means the intervals overlap and all numbers can effectively be made equal. Since a range cannot be negative, return 0.

Why it works

The algorithm works because the score depends only on the largest and smallest values. Any adjustments to middle elements do not affect the final range unless they become new extremes. By maximizing the increase of the smallest element and maximizing the decrease of the largest element, we achieve the smallest possible distance between them. If their adjustable intervals overlap, the score becomes zero.

Python Solution

from typing import List

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        minimum_value = min(nums)
        maximum_value = max(nums)

        reduced_range = maximum_value - minimum_value - 2 * k

        return max(0, reduced_range)

The implementation directly follows the mathematical observation derived earlier.

First, we compute the minimum and maximum values in the array. These are the only two elements that matter for the score calculation.

Next, we calculate how much the range can shrink. Since the smallest value can increase by k and the largest value can decrease by k, the range shrinks by 2 * k.

Finally, we ensure the result is not negative by using max(0, reduced_range).

The solution is concise because the core insight completely eliminates the need for simulation or dynamic programming.

Go Solution

func smallestRangeI(nums []int, k int) int {
    minimumValue := nums[0]
    maximumValue := nums[0]

    for _, value := range nums {
        if value < minimumValue {
            minimumValue = value
        }

        if value > maximumValue {
            maximumValue = value
        }
    }

    reducedRange := maximumValue - minimumValue - 2*k

    if reducedRange < 0 {
        return 0
    }

    return reducedRange
}

The Go implementation follows the same logic as the Python version. Since Go does not provide built-in min() and max() functions for slices, we manually iterate through the array to track the minimum and maximum values.

Integer overflow is not a concern because the constraints are small. The array is guaranteed to contain at least one element, so initializing from nums[0] is safe.

Worked Examples

Example 1

Input: nums = [1], k = 0

Step	Value
Minimum	1
Maximum	1
Original Range	1 - 1 = 0
Reduced Range	0 - 2×0 = 0
Final Answer	0

The array already contains only one value, so the score is zero.

Example 2

Input: nums = [0,10], k = 2

Step	Value
Minimum	0
Maximum	10
Original Range	10
Reduction	2 × 2 = 4
Reduced Range	10 - 4 = 6
Final Answer	6

One valid transformation is:

0  -> 2
10 -> 8

The final range becomes:

8 - 2 = 6

Example 3

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

Step	Value
Minimum	1
Maximum	6
Original Range	5
Reduction	2 × 3 = 6
Reduced Range	5 - 6 = -1
Clamped Result	0

Since the reduced range becomes negative, the adjustable intervals overlap completely.

One valid transformation is:

1 -> 4
3 -> 4
6 -> 4

The final score is:

4 - 4 = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once to find minimum and maximum
Space	O(1)	Only a few variables are used

The algorithm is optimal because every element must be examined at least once to determine the global minimum and maximum. No additional data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        minimum_value = min(nums)
        maximum_value = max(nums)

        reduced_range = maximum_value - minimum_value - 2 * k

        return max(0, reduced_range)

solution = Solution()

assert solution.smallestRangeI([1], 0) == 0  # single element
assert solution.smallestRangeI([0, 10], 2) == 6  # basic shrinking
assert solution.smallestRangeI([1, 3, 6], 3) == 0  # complete overlap
assert solution.smallestRangeI([5, 5, 5], 10) == 0  # all equal values
assert solution.smallestRangeI([1, 100], 0) == 99  # no modification allowed
assert solution.smallestRangeI([1, 100], 50) == 0  # exactly enough reduction
assert solution.smallestRangeI([1, 100], 40) == 19  # partial reduction
assert solution.smallestRangeI([7, 8, 8], 5) == 0  # overlapping intervals
assert solution.smallestRangeI([0, 0, 10000], 10000) == 0  # maximum constraint values
assert solution.smallestRangeI([2, 6, 9, 15], 3) == 7  # general mixed case

Test Summary

Test	Why
`[1], k=0`	Validates single-element handling
`[0,10], k=2`	Verifies standard range shrinking
`[1,3,6], k=3`	Verifies full overlap behavior
`[5,5,5], k=10`	Ensures identical values remain zero
`[1,100], k=0`	Tests no-operation scenario
`[1,100], k=50`	Tests exact elimination of range
`[1,100], k=40`	Tests partial reduction
`[7,8,8], k=5`	Verifies overlapping intervals
`[0,0,10000], k=10000`	Stress test near constraints
`[2,6,9,15], k=3`	General correctness test

Edge Cases

Single Element Array

An array containing only one element always has a score of zero because the minimum and maximum are identical. A naive implementation might still attempt unnecessary calculations or transformations. The current solution handles this naturally because:

$\max(nums)-\min(nums)=0$

so the final answer remains zero.

Large `k` Causing Overlap

When k is large enough, the adjustable intervals of all numbers overlap. This means every value can potentially become the same number. Without careful handling, an implementation might return a negative range. The solution avoids this bug by clamping the answer with:

$\max(0,\ reducedRange)$

No Modification Allowed

When k = 0, no element can change. The answer should therefore equal the original range. Some implementations may incorrectly assume every operation changes the values. In this solution, the formula naturally reduces to:

$\max(nums)-\min(nums)-0$

which preserves the original score exactly.

LeetCode 908 - Smallest Range I

Solution

LeetCode 908 - Smallest Range I

Problem Understanding

Approaches

Brute Force Approach

Optimal Observation

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Single Element Array

Large k Causing Overlap

No Modification Allowed

Large `k` Causing Overlap