Smallest Range II

Medium
1278.

Smallest Range II

Smallest Range II is a medium coding problem on arrays, math and sorting, asked in Google and Adobe interviews.

You are given an integer array nums and an integer k. For every index i you must change nums[i] to either nums[i] + k or nums[i] - k (each index chooses independently).

The score of the resulting array is its maximum element minus its minimum element. Return the smallest score you can achieve.

Example 1

Input
nums = [1], k = 0
Output
0

Example 2

Input
nums = [0,10], k = 2
Output
6
Explanation
Change to [2,8]: the score is 8 - 2 = 6.

Example 3

Input
nums = [1,3,6], k = 3
Output
3
Explanation
Change to [4,6,3]: the score is 6 - 3 = 3.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestRangeII = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Range II — Solution in Python, Java & C++

Smallest Range II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and math.

Smallest Range II is a medium coding problem on arrays, math and sorting, asked in Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Sorting, Greedy
  • Asked at: Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums and an integer k. For every index i you must change nums[i] to either nums[i] + k or nums[i] - k (each index chooses independently).

The score of the resulting array is its maximum element minus its minimum element. Return the smallest score you can achieve.

Example 1

Input: nums = [1], k = 0
Output: 0

Example 2

Input: nums = [0,10], k = 2
Output: 6
Explanation: Change to [2,8]: the score is 8 - 2 = 6.

Example 3

Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change to [4,6,3]: the score is 6 - 3 = 3.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^4
  • 0 <= k <= 10^4

Hints for Smallest Range II

  1. Hint 1

    Sort the array. Is there an optimal choice where the smaller values all go up and the larger values all go down?

  2. Hint 2

    Yes — if some a < b had a going down and b going up, swapping their directions never widens the range. So the answer is a split point: the first i + 1 sorted values get +k, the rest get -k.

  3. Hint 3

    For a split after index i, the maximum is max(a[n-1] - k, a[i] + k) and the minimum is min(a[0] + k, a[i+1] - k). Also consider not splitting at all.

How to solve Smallest Range II

After sorting, some optimal answer adds k to a prefix and subtracts k from the suffix, so only n split points need checking.

Approach

  1. Sort nums into a; the no-split answer (everyone moves the same way) is a[n-1] - a[0].
  2. For each split after index i (from 0 to n−2): the candidates for the maximum are a[i] + k and a[n-1] - k, and for the minimum a[0] + k and a[i+1] - k.
  3. Track the smallest max - min over all splits and return it.

Why it works

Take an optimal assignment where some smaller value a goes down while a larger value b goes up. Swapping them (a up, b down) produces values a + k and b - k, which both lie between a - k and b + k, so the minimum does not drop and the maximum does not rise. Repeating the swap yields an optimal assignment shaped as 'prefix up, suffix down'. In that shape the largest value is either the last raised element or the last element lowered, and the smallest is either the first raised element or the first lowered one, which is exactly what each split computes.

Complexity

  • Time — O(n log n)
  • Space — O(n) for the sorted copy (O(1) extra if sorting in place)

Pitfalls

  • Every element must move — leaving one unchanged is not allowed (that is the variant Smallest Range I relaxes).
  • The all-same-direction case (a[n-1] - a[0]) must be the starting answer; with k = 0 it is the answer.
  • The minimum after a split is not always a[0] + k: the first lowered element a[i+1] - k can be smaller.

Reference solution

Python

from typing import List

def smallestRangeII(nums: List[int], k: int) -> int:
    a = sorted(nums)
    n = len(a)
    best = a[-1] - a[0]
    for i in range(n - 1):
        high = max(a[-1] - k, a[i] + k)
        low = min(a[0] + k, a[i + 1] - k)
        best = min(best, high - low)
    return best

Java

public static int smallestRangeII(int[] nums, int k) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    int best = a[n - 1] - a[0];
    for (int i = 0; i + 1 < n; i++) {
        int high = Math.max(a[n - 1] - k, a[i] + k);
        int low = Math.min(a[0] + k, a[i + 1] - k);
        best = Math.min(best, high - low);
    }
    return best;
}

C++

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

JavaScript

var smallestRangeII = function(nums, k) {
    var a = nums.slice().sort(function(p, q) { return p - q; });
    var n = a.length;
    var best = a[n - 1] - a[0];
    for (var i = 0; i + 1 < n; i++) {
        var high = Math.max(a[n - 1] - k, a[i] + k);
        var low = Math.min(a[0] + k, a[i + 1] - k);
        best = Math.min(best, high - low);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms