Skip to main content
Talentd

Smallest Range II - Solution & Explanation

MediumArrayMathGreedySorting17 min readAsked at: Amazon, Meta, Adobe
Practice this problem

Problem Statement

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

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.

The algorithm first sorts the input array, then calculates the initial difference between the maximum and minimum. It iterates over the array proposing the change boundary at each index, calculating potential new high and low values (by adjusting ends with Ā±k), and preserving the minimal difference found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) if we ignore input space.

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.

With sorted nums, this approach focuses on defining logical min/max around increments/decrements that have the smallest scope impact, using the basic alternative end transforms.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sorting and Checking Potential Breakpoints

Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(1) if we ignore input space.

Direct Calculation of Extremes after Sorting

Time Complexity: O(n log n), Space Complexity: O(1) for array due to in-place.

Greedy + Enumerationā€”

Detailed Complexity Analysis

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

Video Solution

Smallest Range II | Live Coding with Explanation | Leetcode #910 ā€¢ Algorithms Made Easy ā€¢ 7,755 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays