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.

Description Solution Video 5:42

910. Smallest Range II

Medium38.4% acceptance3 companies

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⁴

Asked at 3 companies

Adobe Amazon Meta

Topics

5:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def smallestRangeII(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1]
0

Input

[0,10]
2

Input

[1,3,6]
3

Your code is saved on this device.Solution