910. Smallest Range II - Solution & Explanation

Q: Is Smallest Range II easy or hard?

Smallest Range II is classified as a Medium problem. The implementation is short, but the greedy insight that the optimal solution comes from a single breakpoint after sorting is not immediately obvious.

Q: How to solve Smallest Range II in O(n)?

A fully O(n) solution is not typical because the algorithm relies on sorting the array to reason about boundaries. After sorting in O(n log n), the remaining logic is O(n). The scan computes adjusted extremes using values like nums[i] + K and nums[i+1] - K to track the smallest possible range.

Q: What is the best approach for Smallest Range II?

The best approach is a greedy strategy after sorting the array. Once sorted, assume elements on the left increase by K and elements on the right decrease by K. Checking every possible split point lets you compute the new minimum and maximum efficiently, resulting in O(n log n) time due to sorting and O(1) extra space.

Q: Is Smallest Range II asked at Google/Amazon/Meta?

Greedy array problems similar to Smallest Range II appear frequently in interviews at companies like Google, Amazon, and Meta. The question tests sorting, greedy reasoning, and the ability to reduce exponential choices into a linear scan after ordering the data.

Q: What data structure is used in Smallest Range II?

The primary data structure is a simple array. The algorithm relies on sorting the array and scanning it once to evaluate candidate ranges. No additional structures such as heaps or hash maps are required.

Q: What is the time complexity of Smallest Range II?

The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan evaluates all possible breakpoints in O(n) time. Space complexity is O(1) if sorting is done in place.

Q: Smallest Range II Python or Java solution approach?

Python, Java, C++, and similar languages follow the same logic: sort the array, initialize the base range, then iterate through possible split points to compute new min and max values. Each iteration updates the minimum range using the greedy boundary formula.

The problem

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

For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.

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

Return the minimum score of nums after changing the values at each index.

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: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.

Constraints:

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

Approach overview

Problem Overview: You are given an integer array where each element can either increase by K or decrease by K. After applying this change exactly once to every element, the goal is to minimize the difference between the maximum and minimum values in the final array.

The brute force idea is to try every possible combination of adding or subtracting K, but that leads to 2^n possibilities and becomes infeasible quickly. The key observation is that once the array is sorted, the optimal solution always forms a clear boundary: numbers on the left increase by K, and numbers on the right decrease by K. This insight reduces the search space dramatically.

Approach 1: Sorting and Checking Potential Breakpoints (O(n log n) time, O(1) space)

Sort the array first. After sorting, consider a breakpoint between indices i and i+1. All elements from 0..i are increased by K, and all elements from i+1..n-1 are decreased by K. For each breakpoint, compute the new minimum and maximum values. The new maximum is the larger of nums[i] + K and nums[n-1] - K. The new minimum is the smaller of nums[0] + K and nums[i+1] - K. Iterate through every possible breakpoint and keep the smallest range. Sorting costs O(n log n), while the single pass evaluation is O(n). This method relies on a classic greedy observation that only boundary transitions matter.

Approach 2: Direct Calculation of Extremes after Sorting (O(n log n) time, O(1) space)

This approach simplifies the same greedy idea by focusing directly on how the extreme values change after modification. Start with the original range nums[n-1] - nums[0]. After sorting, assume the smallest values will increase by K and the largest values will decrease by K. Scan the array once and evaluate candidate ranges using the adjusted extremes: high = max(nums[n-1] - K, nums[i] + K) and low = min(nums[0] + K, nums[i+1] - K). Update the minimum range across all splits. The reasoning comes from how array ordering limits which elements can become the new extremes.

Recommended for interviews: Interviewers expect the greedy + sorting solution. Start by explaining the brute force intuition to show you understand the full search space, then pivot to the key observation: once sorted, the optimal configuration always splits the array into two groups. Implementing the breakpoint scan in O(n) after sorting demonstrates strong algorithmic reasoning and familiarity with greedy boundary problems.

Approach 1: Sorting and Checking Potential Breakpoints

After sorting the array, our potential strategy is to focus on bridging the maximum and minimum gap by controlling possible breakpoints where the boundary conditions for minimum and maximum flip due to the presorted state.

Python

def smallestRangeII(nums, k):
    nums.sort()
    result = nums[-1] - nums[0]
    for i in range(len(nums) - 1):
        high = max(nums[i] + k, nums[-1] - k)
        low = min(nums[0] + k, nums[i + 1] - k)
        result = min(result, high - low)
    return result

nums = [1, 3, 6]
k = 3
print(smallestRangeII(nums, k))  # Output: 3

Java

import java.util.Arrays;

public class SmallestRangeII {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int result = nums[nums.length - 1] - nums[0];
        for (int i = 0; i < nums.length - 1; i++) {
            int high = Math.max(nums[i] + k, nums[nums.length - 1] - k);
            int low = Math.min(nums[0] + k, nums[i + 1] - k);
            result = Math.min(result, high - low);
        }
        return result;
    }

    public static void main(String[] args) {
        SmallestRangeII obj = new SmallestRangeII();
        int[] nums = {1, 3, 6};
        int k = 3;
        System.out.println(obj.smallestRangeII(nums, k));  // Output: 3
    }
}

C++

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int smallestRangeII(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int result = nums.back() - nums.front();
    for (int i = 0; i < nums.size() - 1; ++i) {
        int high = max(nums[i] + k, nums.back() - k);
        int low = min(nums.front() + k, nums[i + 1] - k);
        result = min(result, high - low);
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, 6};
    int k = 3;
    int result = smallestRangeII(nums, k);
    return 0;
}

JavaScript

function smallestRangeII(nums, k) {
    nums.sort((a, b) => a - b);
    let result = nums[nums.length - 1] - nums[0];
    for (let i = 0; i < nums.length - 1; i++) {
        let high = Math.max(nums[i] + k, nums[nums.length - 1] - k);
        let low = Math.min(nums[0] + k, nums[i + 1] - k);
        result = Math.min(result, high - low);
    }
    return result;
}

const nums = [1, 3, 6];
const k = 3;
console.log(smallestRangeII(nums, k));  // Output: 3

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int smallestRangeII(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    int result = nums[numsSize - 1] - nums[0];
    for (int i = 0; i < numsSize - 1; i++) {
        int high = fmax(nums[i] + k, nums[numsSize - 1] - k);
        int low = fmin(nums[0] + k, nums[i + 1] - k);
        result = fmin(result, high - low);
    }
    return result;
}

int main() {
    int nums[] = {1, 3, 6};
    int k = 3;
    int result = smallestRangeII(nums, 3, k);
    printf("%d\n", result);  // Output: 3
    return 0;
}

using System;

public class SmallestRange {
    public int SmallestRangeII(int[] nums, int k) {
        Array.Sort(nums);
        int result = nums[nums.Length - 1] - nums[0];
        for (int i = 0; i < nums.Length - 1; i++) {
            int high = Math.Max(nums[i] + k, nums[nums.Length - 1] - k);
            int low = Math.Min(nums[0] + k, nums[i + 1] - k);
            result = Math.Min(result, high - low);
        }
        return result;
    }

    public static void Main(string[] args) {
        SmallestRange sr = new SmallestRange();
        int[] nums = {1, 3, 6};
        int k = 3;
        Console.WriteLine(sr.SmallestRangeII(nums, k)); // Output: 3
    }
}

This Python code focuses on calculating different potential optimal ranges by adjusting endpoints dynamically around sorted points with ±k considerations.

Complexity

Time Complexity: O(n log n), Space Complexity: O(1) excluding input storage.

Try this approach in the editor

Approach 2: Direct Calculation of Extremes after Sorting

A slight variation that considers minimizing and maximizing simultaneously, with the goal of finding directly altered extremes without sequence traversals.

Python

def smallestRangeII(nums, k):
    nums.sort()
    min_val = nums[0] + k
    max_val = nums[-1] - k
    result = nums[-1] - nums[0]

    for i in range(len(nums) - 1):
        current_max = max(nums[i] + k, max_val)
        current_min = min(min_val, nums[i + 1] - k)
        result = min(result, current_max - current_min)

    return result

nums = [1, 3, 6]
k = 3
print(smallestRangeII(nums, k))  # Output: 3

Java

import java.util.*;

public class SmallestRangeII {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int minVal = nums[0] + k, maxVal = nums[nums.length - 1] - k;
        int result = nums[nums.length - 1] - nums[0];

        for (int i = 0; i < nums.length - 1; i++) {
            int currentMax = Math.max(nums[i] + k, maxVal);
            int currentMin = Math.min(minVal, nums[i + 1] - k);
            result = Math.min(result, currentMax - currentMin);
        }
        return result;
    }

    public static void main(String[] args) {
        SmallestRangeII solution = new SmallestRangeII();
        int k = 3;
        int[] nums = {1, 3, 6};
        System.out.println(solution.smallestRangeII(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int smallestRangeII(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int minVal = nums[0] + k, maxVal = nums.back() - k;
    int result = nums.back() - nums[0];

    for (int i = 0; i < nums.size() - 1; ++i) {
        int currentMax = max(nums[i] + k, maxVal);
        int currentMin = min(minVal, nums[i + 1] - k);
        result = min(result, currentMax - currentMin);
    }
    return result;
}

int main() {
    vector<int> nums = {1, 3, 6};
    int k = 3;
    cout << "Result: " << smallestRangeII(nums, k) << endl;
    return 0;
}

JavaScript

function smallestRangeII(nums, k) {
    nums.sort((a, b) => a - b);
    let minVal = nums[0] + k, maxVal = nums[nums.length - 1] - k;
    let result = nums[nums.length - 1] - nums[0];

    for (let i = 0; i < nums.length - 1; i++) {
        let currentMax = Math.max(nums[i] + k, maxVal);
        let currentMin = Math.min(minVal, nums[i + 1] - k);
        result = Math.min(result, currentMax - currentMin);
    }

    return result;
}

const nums = [1, 3, 6];
const k = 3;
console.log(smallestRangeII(nums, k));  // Output: 3

#include<stdlib.h>
#include<stdio.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int smallestRangeII(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    int minVal = nums[0] + k, maxVal = nums[numsSize - 1] - k;
    int result = nums[numsSize - 1] - nums[0];

    for (int i = 0; i < numsSize - 1; i++) {
        int currentMax = fmax(nums[i] + k, maxVal);
        int currentMin = fmin(minVal, nums[i + 1] - k);
        result = fmin(result, currentMax - currentMin);
    }
    return result;
}

int main() {
    int nums[] = {1, 3, 6};
    int k = 3;
    int result = smallestRangeII(nums, 3, k);
    printf("Result: %d\n", result);
    return 0;
}

using System;

public class SmallestRangeII {
    public int SmallestRange(int[] nums, int k) {
        Array.Sort(nums);
        int minVal = nums[0] + k;
        int maxVal = nums[nums.Length - 1] - k;
        int result = nums[nums.Length - 1] - nums[0];

        for (int i = 0; i < nums.Length - 1; i++) {
            int currentMax = Math.Max(nums[i] + k, maxVal);
            int currentMin = Math.Min(minVal, nums[i + 1] - k);
            result = Math.Min(result, currentMax - currentMin);
        }

        return result;
    }

    public static void Main(string[] args) {
        SmallestRangeII solution = new SmallestRangeII();
        int[] nums = {1, 3, 6};
        int k = 3;
        Console.WriteLine(solution.SmallestRange(nums, k));
    }
}

In Python, this keeps consistent usage of boundary establishment on spread, anchoring minimal/maximal values using iteratively considered derivations.

Complexity

Time Complexity: O(n log n), Space Complexity: O(1).

Try this approach in the editor

Approach 3: Greedy + Enumeration

According to the problem requirements, we need to find the minimum difference between the maximum and minimum values in the array. Each element can be increased or decreased by k, so we can divide the elements in the array into two parts, one part increased by k and the other part decreased by k. Therefore, we should decrease the larger values in the array by k and increase the smaller values by k to ensure the minimum difference between the maximum and minimum values.

Therefore, we can first sort the array, then enumerate each element in the array, divide it into two parts, one part increased by k and the other part decreased by k, and calculate the difference between the maximum and minimum values. Finally, take the minimum value among all differences.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array.

TypeScript

function smallestRangeII(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = nums.at(-1)! - nums[0];
    for (let i = 1; i < nums.length; ++i) {
        const mi = Math.min(nums[0] + k, nums[i] - k);
        const mx = Math.max(nums.at(-1)! - k, nums[i - 1] + k);
        ans = Math.min(ans, mx - mi);
    }
    return ans;
}

func smallestRangeII(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := nums[n-1] - nums[0]
	for i := 1; i < n; i++ {
		mi := min(nums[0]+k, nums[i]-k)
		mx := max(nums[i-1]+k, nums[n-1]-k)
		ans = min(ans, mx-mi)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting and Checking Potential Breakpoints	Time Complexity: O(n log n), Space Complexity: O(1) excluding input storage.
Direct Calculation of Extremes after Sorting	Time Complexity: O(n log n), Space Complexity: O(1).
Greedy + Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting and Checking Potential Breakpoints	O(n log n)	O(1)	Standard greedy solution when you want to explicitly evaluate each possible split after sorting
Direct Calculation of Extremes after Sorting	O(n log n)	O(1)	Cleaner implementation when you directly compute adjusted min/max values while scanning the sorted array

Frequently asked questions

Is Smallest Range II easy or hard?

Smallest Range II is classified as a Medium problem. The implementation is short, but the greedy insight that the optimal solution comes from a single breakpoint after sorting is not immediately obvious.

How to solve Smallest Range II in O(n)?

A fully O(n) solution is not typical because the algorithm relies on sorting the array to reason about boundaries. After sorting in O(n log n), the remaining logic is O(n). The scan computes adjusted extremes using values like nums[i] + K and nums[i+1] - K to track the smallest possible range.

What is the best approach for Smallest Range II?

The best approach is a greedy strategy after sorting the array. Once sorted, assume elements on the left increase by K and elements on the right decrease by K. Checking every possible split point lets you compute the new minimum and maximum efficiently, resulting in O(n log n) time due to sorting and O(1) extra space.

Is Smallest Range II asked at Google/Amazon/Meta?

Greedy array problems similar to Smallest Range II appear frequently in interviews at companies like Google, Amazon, and Meta. The question tests sorting, greedy reasoning, and the ability to reduce exponential choices into a linear scan after ordering the data.

What data structure is used in Smallest Range II?

The primary data structure is a simple array. The algorithm relies on sorting the array and scanning it once to evaluate candidate ranges. No additional structures such as heaps or hash maps are required.

What is the time complexity of Smallest Range II?

The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan evaluates all possible breakpoints in O(n) time. Space complexity is O(1) if sorting is done in place.

Smallest Range II Python or Java solution approach?

Python, Java, C++, and similar languages follow the same logic: sort the array, initialize the base range, then iterate through possible split points to compute new min and max values. Each iteration updates the minimum range using the greedy boundary formula.

Smallest Range II solution and explanation

The problem

Approach overview

Approach 1: Sorting and Checking Potential Breakpoints

Approach 2: Direct Calculation of Extremes after Sorting

Approach 3: Greedy + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Smallest Range II solution and explanation

The problem

Approach overview

Approach 1: Sorting and Checking Potential Breakpoints

Approach 2: Direct Calculation of Extremes after Sorting

Approach 3: Greedy + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems