Smallest Range I

Easy

#0862Time: O(N log N), where N is the number of elements in `nums`. This is because sorting the array takes O(N log N) time, which dominates the other constant-time operations.Space: O(log N) or O(N), depending on the implementation of the sorting algorithm used by the language's standard library. For example, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.

Patterns

Math

Data structures

Array

Prompt

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

Example 1:

Input: nums = [1], k = 0
Output: 0
Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2:

Input: nums = [0,10], k = 2
Output: 6
Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3:

Input: nums = [1,3,6], k = 3
Output: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves sorting the array first to easily find the minimum and maximum elements. Once the array is sorted, the minimum element is the first element and the maximum is the last. With these values, we can calculate the smallest possible range.

Algorithm

Handle the edge case where the array has only one element. In this case, the range is always 0.
Sort the input array nums in non-decreasing order.
Identify the minimum value as min_val = nums[0].
Identify the maximum value as max_val = nums[nums.length - 1].
Calculate the initial difference: diff = max_val - min_val.
If diff <= 2 * k, it's possible to make all elements equal, so the minimum score is 0. Return 0.
Otherwise, the minimum score is diff - 2 * k. Return this value.
This can be concisely written as return Math.max(0, max_val - min_val - 2 * k);

1import java.util.Arrays;2 3class Solution {4    public int smallestRangeI(int[] nums, int k) {5        if (nums.length == 1) {6            return 0;7        }8        Arrays.sort(nums);9        int minVal = nums[0];10        int maxVal = nums[nums.length - 1];11        int diff = maxVal - minVal;12        return Math.max(0, diff - 2 * k);13    }14}

Walkthrough

The core idea is that to minimize the difference max(nums) - min(nums), we should aim to increase the minimum value and decrease the maximum value. The maximum possible value for the new minimum is original_min + k. The minimum possible value for the new maximum is original_max - k. By sorting the array nums, we can find the original minimum (nums[0]) and maximum (nums[nums.length - 1]) in O(1) time after the sort. The potential new range would be (original_max - k) - (original_min + k), which simplifies to original_max - original_min - 2k. If this difference is negative, it means the range [original_max - k, original_min + k] is overlapping. This implies we can make all elements equal to some value within this overlap, resulting in a score of 0. Therefore, the smallest possible score is max(0, (nums[nums.length - 1] - nums[0]) - 2 * k). The algorithm is as follows:

Complexity

Time

O(N log N), where N is the number of elements in `nums`. This is because sorting the array takes O(N log N) time, which dominates the other constant-time operations.

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm used by the language's standard library. For example, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.

Trade-offs

Pros

Simple to understand and implement.
Correctly identifies the minimum and maximum values needed for the calculation.

Cons

The sorting step is unnecessary and makes the algorithm less efficient than it could be.
Time complexity is dominated by the sort, which is not optimal for this problem.

A more efficient approach avoids sorting by finding the minimum and maximum elements in a single pass through the array. This reduces the time complexity from O(N log N) to O(N).

Algorithm

Handle the edge case where the array has only one element, returning 0.
Initialize min_val to nums[0] and max_val to nums[0].
Iterate through the array nums from the second element.
In each iteration, update the minimum: min_val = Math.min(min_val, nums[i]).
In each iteration, update the maximum: max_val = Math.max(max_val, nums[i]).
After the loop finishes, calculate the result: result = max_val - min_val - 2 * k.
Since the score cannot be negative, return Math.max(0, result).

1class Solution {2    public int smallestRangeI(int[] nums, int k) {3        if (nums.length == 1) {4            return 0;5        }6        int minVal = nums[0];7        int maxVal = nums[0];8        for (int i = 1; i < nums.length; i++) {9            minVal = Math.min(minVal, nums[i]);10            maxVal = Math.max(maxVal, nums[i]);11        }12        int diff = maxVal - minVal;13        return Math.max(0, diff - 2 * k);14    }15}

Walkthrough

The logic remains the same as the sorting approach: the goal is to minimize the range by increasing the smallest element and decreasing the largest element. The key insight is that we only need the original minimum and maximum values, not the entire sorted array. We can find these two values by iterating through the array just once. We initialize two variables, min_val and max_val, with the value of the first element. During the iteration, we update min_val and max_val whenever we encounter a smaller or larger element, respectively. After the single pass, we have the required min_val and max_val. The final calculation is identical to the previous approach: max(0, max_val - min_val - 2 * k). The algorithm is as follows:

Complexity

Time

O(N), where N is the number of elements in `nums`. We iterate through the array once to find the minimum and maximum values.

Space

O(1), as we only use a constant amount of extra space for variables like `minVal` and `maxVal`.

Trade-offs

Pros

Optimal time complexity as it requires only one pass through the array.
Minimal space usage (O(1)).
Simple and efficient.

Cons

No significant cons for this problem as it is optimal.

Solutions

Solution

1class Solution { public int smallestRangeI ( int [] nums , int k ) { int mx = 0 ; int mi = 10000 ; for ( int v : nums ) { mx = Math . max ( mx , v ); mi = Math . min ( mi , v ); } return Math . max ( 0 , mx - mi - k * 2 ); } }

1class Solution { public: int smallestRangeI ( vector < int >& nums , int k ) { auto [ mi , mx ] = minmax_element ( nums . begin (), nums . end ()); return max ( 0 , * mx - * mi - k * 2 ); } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem