908. Smallest Range I - Solution & Code

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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⁴

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.

Python

def smallestRangeI(nums, k):
    min_elem = min(nums)
    max_elem = max(nums)
    return max(0, (max_elem - min_elem) - 2 * k)

Java

import java.util.*;

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

C++

#include <vector>
#include <algorithm>

int smallestRangeI(std::vector<int>& nums, int k) {
    int minElem = *std::min_element(nums.begin(), nums.end());
    int maxElem = *std::max_element(nums.begin(), nums.end());
    int result = maxElem - minElem - 2 * k;
    return result > 0 ? result : 0;
}

JavaScript

function smallestRangeI(nums, k) {
    let min = Math.min(...nums);
    let max = Math.max(...nums);
    return Math.max(0, max - min - 2 * k);
}

#include <stdio.h>

int smallestRangeI(int* nums, int numsSize, int k) {
    int min = nums[0], max = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] < min) min = nums[i];
        if (nums[i] > max) max = nums[i];
    }
    int score = max - min - 2 * k;
    return score > 0 ? score : 0;
}

public class Solution {
    public int SmallestRangeI(int[] nums, int k) {
        int min = int.MaxValue, max = int.MinValue;
        foreach (int num in nums) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        int score = max - min - 2 * k;
        return score > 0 ? score : 0;
    }
}

This Python solution finds the minimum and maximum elements using the built-in min() and max() functions. It calculates the score after potentially adjusting the elements by k, and takes the maximum between 0 and the computed score to ensure non-negative results.

Complexity

Time Complexity: O(n) for min and max functions.
Space Complexity: O(1).

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.

Python

import sys

def compute_score(nums, adjustments):
    min_val = sys.maxsize
    max_val = -sys.maxsize - 1
    for i, num in enumerate(nums):
        adjusted = num + adjustments[i]
        min_val = min(min_val, adjusted)
        max_val = max(max_val, adjusted)
    return max_val - min_val


def adjust_all(k, idx, nums, adjustments, best_score):
    if idx == len(nums):
        current_score = compute_score(nums, adjustments)
        best_score[0] = min(best_score[0], current_score)
        return
    for adjustment in range(-k, k+1):
        adjustments[idx] = adjustment
        adjust_all(k, idx + 1, nums, adjustments, best_score)


def smallest_range_i_brute_force(nums, k):
    best_score = [sys.maxsize]
    adjust_all(k, 0, nums, [0] * len(nums), best_score)
    return best_score[0]

Java

import java.util.*;

public class Solution {
    private int computeScore(int[] nums, int[] adjustments) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; ++i) {
            int adjusted = nums[i] + adjustments[i];
            min = Math.min(min, adjusted);
            max = Math.max(max, adjusted);
        }
        return max - min;
    }

    private void adjustAll(int k, int idx, int[] nums, int[] adjustments, int[] bestScore) {
        if (idx == nums.length) {
            int currentScore = computeScore(nums, adjustments);
            bestScore[0] = Math.min(bestScore[0], currentScore);
            return;
        }
        for (int adjustment = -k; adjustment <= k; ++adjustment) {
            adjustments[idx] = adjustment;
            adjustAll(k, idx + 1, nums, adjustments, bestScore);
        }
    }

    public int smallestRangeIBruteForce(int[] nums, int k) {
        int[] bestScore = {Integer.MAX_VALUE};
        adjustAll(k, 0, nums, new int[nums.length], bestScore);
        return bestScore[0];
    }
}

C++

#include <vector>
#include <climits>

int computeScore(const std::vector<int>& nums, const std::vector<int>& adjustments) {
    int minElem = INT_MAX, maxElem = INT_MIN;
    for (size_t i = 0; i < nums.size(); ++i) {
        int adjusted = nums[i] + adjustments[i];
        minElem = std::min(minElem, adjusted);
        maxElem = std::max(maxElem, adjusted);
    }
    return maxElem - minElem;
}

void adjustAll(int k, size_t idx, std::vector<int>& nums, std::vector<int>& adjustments, int& bestScore) {
    if (idx == nums.size()) {
        int currentScore = computeScore(nums, adjustments);
        bestScore = std::min(bestScore, currentScore);
        return;
    }
    for (int adjustment = -k; adjustment <= k; ++adjustment) {
        adjustments[idx] = adjustment;
        adjustAll(k, idx + 1, nums, adjustments, bestScore);
    }
}

int smallestRangeIBruteForce(std::vector<int>& nums, int k) {
    int bestScore = INT_MAX;
    std::vector<int> adjustments(nums.size());
    adjustAll(k, 0, nums, adjustments, bestScore);
    return bestScore;
}

JavaScript

function computeScore(nums, adjustments) {
    let min = Infinity;
    let max = -Infinity;
    for (let i = 0; i < nums.length; ++i) {
        const adjusted = nums[i] + adjustments[i];
        min = Math.min(min, adjusted);
        max = Math.max(max, adjusted);
    }
    return max - min;
}

function adjustAll(k, idx, nums, adjustments, bestScore) {
    if (idx === nums.length) {
        const currentScore = computeScore(nums, adjustments);
        bestScore[0] = Math.min(bestScore[0], currentScore);
        return;
    }
    for (let adjustment = -k; adjustment <= k; ++adjustment) {
        adjustments[idx] = adjustment;
        adjustAll(k, idx + 1, nums, adjustments, bestScore);
    }
}

function smallestRangeIBruteForce(nums, k) {
    const bestScore = [Infinity];
    adjustAll(k, 0, nums, new Array(nums.length).fill(0), bestScore);
    return bestScore[0];
}

#include <stdio.h>
#include <limits.h>

int computeScore(int nums[], int numsSize, int adjustments[]) {
    int min = INT_MAX, max = INT_MIN;
    for (int i = 0; i < numsSize; ++i) {
        int adjusted = nums[i] + adjustments[i];
        if (adjusted < min) min = adjusted;
        if (adjusted > max) max = adjusted;
    }
    return max - min;
}

void adjustAll(int k, int idx, int numsSize, int nums[], int adjustments[], int *bestScore) {
    if (idx == numsSize) {
        int currentScore = computeScore(nums, numsSize, adjustments);
        if (currentScore < *bestScore) {
            *bestScore = currentScore;
        }
        return;
    }
    for (int adjustment = -k; adjustment <= k; ++adjustment) {
        adjustments[idx] = adjustment;
        adjustAll(k, idx + 1, numsSize, nums, adjustments, bestScore);
    }
}

int smallestRangeIBruteForce(int* nums, int numsSize, int k) {
    int bestScore = INT_MAX;
    int adjustments[numsSize];
    adjustAll(k, 0, numsSize, nums, adjustments, &bestScore);
    return bestScore;
}

using System;

public class Solution {
    private int ComputeScore(int[] nums, int[] adjustments) {
        int min = int.MaxValue;
        int max = int.MinValue;
        for (int i = 0; i < nums.Length; ++i) {
            int adjusted = nums[i] + adjustments[i];
            if (adjusted < min) min = adjusted;
            if (adjusted > max) max = adjusted;
        }
        return max - min;
    }

    private void AdjustAll(int k, int idx, int[] nums, int[] adjustments, ref int bestScore) {
        if (idx == nums.Length) {
            int currentScore = ComputeScore(nums, adjustments);
            if (currentScore < bestScore) bestScore = currentScore;
            return;
        }
        for (int adjustment = -k; adjustment <= k; ++adjustment) {
            adjustments[idx] = adjustment;
            AdjustAll(k, idx + 1, nums, adjustments, ref bestScore);
        }
    }

    public int SmallestRangeIBruteForce(int[] nums, int k) {
        int bestScore = int.MaxValue;
        int[] adjustments = new int[nums.Length];
        AdjustAll(k, 0, nums, adjustments, ref bestScore);
        return bestScore;
    }
}

The Python brute force code systematically explores every possible adjustment for each element to potentially minimize the range. It is useful for understanding recursive tree depth adjustments, but too slow for very large n.

Complexity

Time Complexity: O(n * 2^(n * k)).
Space Complexity: O(n).

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).

TypeScript

function smallestRangeI(nums: number[], k: number): number {
    const mx = Math.max(...nums);
    const mi = Math.min(...nums);
    return Math.max(mx - mi - k * 2, 0);
}

func smallestRangeI(nums []int, k int) int {
	mi, mx := slices.Min(nums), slices.Max(nums)
	return max(0, mx-mi-k*2)
}

Rust

impl Solution {
    pub fn smallest_range_i(nums: Vec<i32>, k: i32) -> i32 {
        let max = nums.iter().max().unwrap();
        let min = nums.iter().min().unwrap();
        (0).max(max - min - k * 2)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Adjusting Max and Min	Time Complexity: O(n) for min and max functions. Space Complexity: O(1).
Brute Force Adjustment Simulation	Time Complexity: O(n * 2^(n * k)). Space Complexity: O(n).
Mathematics	–

Complexity analysis

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

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.

Smallest Range I solution and explanation

The problem

Approach overview

Approach 1: Adjusting Max and Min

Approach 2: Brute Force Adjustment Simulation

Approach 3: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Smallest Range I solution and explanation

The problem

Approach overview

Approach 1: Adjusting Max and Min

Approach 2: Brute Force Adjustment Simulation

Approach 3: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems