Skip to main content
Talentd

Smallest Range I - Solution & Explanation

EasyArrayMath16 min readAsked at: Adobe, Google, Glassdoor
Practice this problem

Problem Statement

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 <= 104
  • 0 <= nums[i] <= 104
  • 0 <= k <= 104

Approach Overview

Problem Overview: You are given an integer array and a value k. For every element, you can either add k or subtract k. After performing this operation once on each element, the goal is to minimize the difference between the maximum and minimum values in the array.

Approach 1: Brute Force Adjustment Simulation (O(n²) time, O(1) space)

The brute force idea is to simulate possible adjustments and observe how the minimum and maximum values change. For each element, consider it as a potential minimum after applying +k, and for every other element consider applying -k to see if it becomes the maximum. Iterate over pairs of elements and compute the resulting range after adjustments. This approach explicitly evaluates combinations of adjustments to see which produces the smallest range. While straightforward, it performs redundant comparisons and scales poorly for large arrays because every candidate pair requires recomputing the resulting minimum and maximum.

This method helps build intuition about how adding or subtracting k shifts values toward or away from the center of the distribution. However, the nested iteration results in O(n²) time complexity, making it inefficient when n grows.

Approach 2: Adjusting Max and Min (O(n) time, O(1) space)

The key observation is that every element can move within the range [nums[i] - k, nums[i] + k]. To minimize the final spread, you want to push large values downward and small values upward. The maximum possible reduction happens when the original maximum decreases by k and the original minimum increases by k.

Compute the current minimum and maximum in the array using a single pass. The original range is maxVal - minVal. After adjustment, the best possible range becomes (maxVal - k) - (minVal + k), which simplifies to maxVal - minVal - 2k. If this value becomes negative, the range cannot go below zero, so clamp the result using max(0, maxVal - minVal - 2k). This insight removes the need to simulate every adjustment and reduces the problem to a simple scan.

This approach relies on properties of array traversal and basic math reasoning. Because only the global minimum and maximum matter, the algorithm runs in linear time with constant memory.

Recommended for interviews: Interviewers typically expect the max–min adjustment insight. Demonstrating the brute force reasoning first shows you understand the problem constraints, but quickly deriving the max(0, max - min - 2k) formula signals strong problem-solving and pattern recognition skills.

Approach 1: Adjusting Max and Min

This approach leverages the concept that if we can adjust elements of the array within the range [-k, k], the maximum score will be the difference between (max(nums) - k) and (min(nums) + k). If this difference is negative or zero, the minimum score is 0, reflecting perfect minimizing of the range.

We can calculate the adjusted minimum possible score directly without iterating over the array repeatedly.

The code first determines the current minimum and maximum in the array. It then computes the potential adjusted score by subtracting 2 * k from the difference between the maximum and minimum. If this resulting score is negative, the answer is 0 because we can perfectly equalize the values with adjustments. Otherwise, it returns the calculated score.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array, as we are scanning through the array to find the min and max.
Space Complexity: O(1), as we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Brute Force Adjustment Simulation

Another method includes simulating each possible adjustment operation, iterating each possibility within [-k, k] for each index. Though practically inefficient for large inputs, it demonstrates comprehension of adjustments and their effects.

This brute force version simulates every possible permutation of adjustments for each index within the allowable range [-k, k]. For each complete permutation, it computes the resultant score and tracks the minimum found across all permutations. Though conceptually straightforward, it is inefficient (O(n * 2^(n * k))) for large n.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 2^(n * k)), impractical for large n due to exponential growth.
Space Complexity: O(n) for storing adjustments.

Try this approach in the editor →

Approach 3: Mathematics

According to the problem description, we can subtract k from the maximum value in the array and add k to the minimum value in the array, which can reduce the difference between the maximum and minimum values in the array.

Therefore, the final answer is the larger value between max(nums) - min(nums) - 2 times k and 0.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Adjusting Max and Min

Time Complexity: O(n), where n is the length of the array, as we are scanning through the array to find the min and max.
Space Complexity: O(1), as we are using a constant amount of extra space.

Brute Force Adjustment Simulation

Time Complexity: O(n * 2^(n * k)), impractical for large n due to exponential growth.
Space Complexity: O(n) for storing adjustments.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Adjustment SimulationO(n²)O(1)Useful for understanding how ±k adjustments affect pairwise min/max values
Adjusting Max and MinO(n)O(1)Optimal approach when only the global min and max determine the final range

Video Solution

LeetCode Smallest Range I Solution Explained - Java • Nick White • 8,213 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Range I easy or hard?
Smallest Range I is classified as an Easy problem on LeetCode with a high acceptance rate. The main challenge is recognizing that only the global minimum and maximum affect the final range after applying ±k adjustments.
Smallest Range I Python/Java solution
In Python or Java, iterate through the array to compute min and max values, then return max(0, maxVal - minVal - 2 * k). The implementation is only a few lines and runs in O(n) time with constant extra space.
How to solve Smallest Range I in O(n)?
Traverse the array once to compute the smallest and largest values. The initial range is maxVal - minVal. After applying ±k adjustments, the smallest possible range becomes max(0, maxVal - minVal - 2k). This avoids simulating every operation and keeps the algorithm linear.
What is the best approach for Smallest Range I?
The optimal approach computes the original minimum and maximum values in the array and applies the formula max(0, maxVal - minVal - 2k). Increasing the minimum by k and decreasing the maximum by k gives the smallest possible spread. This method runs in O(n) time and O(1) space.
Is Smallest Range I asked at Google/Amazon/Meta?
Problems based on array range manipulation and greedy adjustment patterns appear in interviews at companies like Amazon and Meta. While this exact problem may not always appear, the reasoning about minimizing ranges and analyzing bounds is commonly tested.
What data structure is used in Smallest Range I?
The problem primarily uses a simple array traversal. No advanced data structures are required because the solution depends only on tracking the current minimum and maximum values while iterating through the array.
What is the time complexity of Smallest Range I?
The optimal solution runs in O(n) time because it scans the array once to find the minimum and maximum values. The space complexity is O(1) since only a few variables are required. Brute force simulations can take O(n²) time due to repeated comparisons.

Ready to solve this problem?

Practice Smallest Range I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays