Smallest Range I

Easy
360.

Smallest Range I

Smallest Range I is an easy coding problem on arrays and math, asked in Amazon and Adobe interviews.

You are given an integer array nums and an integer k. For each index you may change nums[i] to any value in the range [nums[i] - k, nums[i] + k], once.

Return the minimum possible difference between the largest and smallest value of the resulting array.

Example 1

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

Example 2

Input
nums = [0,10], k = 2
Output
6
Explanation
Turn [0,10] into [2,8].

Example 3

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

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 10000
  • 0 <= k <= 10000
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 smallestRangeI = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

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

Smallest Range I is an easy coding problem on arrays and math, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math
  • Asked at: Amazon, 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 each index you may change nums[i] to any value in the range [nums[i] - k, nums[i] + k], once.

Return the minimum possible difference between the largest and smallest value of the resulting array.

Example 1

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

Example 2

Input: nums = [0,10], k = 2
Output: 6
Explanation: Turn [0,10] into [2,8].

Example 3

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

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 10000
  • 0 <= k <= 10000

Hints for Smallest Range I

  1. Hint 1

    Only the current minimum and maximum matter — everything else can be moved inside whatever gap they leave.

  2. Hint 2

    Raise the minimum by k and lower the maximum by k.

  3. Hint 3

    If they cross, the whole array can be made equal, so the answer is 0 rather than a negative number.

How to solve Smallest Range I

Only the extremes matter: raise the minimum by k, lower the maximum by k, and clamp at zero.

Approach

  1. Return max(0, max(nums) - min(nums) - 2k).

Why it works

Every element can be shifted independently, and any element between the new min and max can be left alone or moved inside; if the shifted extremes cross, everything can be made equal.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Without the clamp the answer goes negative when 2k exceeds the spread.

Reference solution

Python

def smallestRangeI(nums, k: int) -> int:
    return max(0, max(nums) - min(nums) - 2 * k)

Java

public static int smallestRangeI(int[] nums, int k) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        lo = Math.min(lo, x);
        hi = Math.max(hi, x);
    }
    return Math.max(0, hi - lo - 2 * k);
}

C++

int smallestRangeI(vector<int>& nums, int k) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        lo = min(lo, x);
        hi = max(hi, x);
    }
    return max(0, hi - lo - 2 * k);
}

JavaScript

var smallestRangeI = function(nums, k) {
    let lo = nums[0], hi = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < lo) lo = nums[i];
        if (nums[i] > hi) hi = nums[i];
    }
    const span = hi - lo - 2 * k;
    return span > 0 ? span : 0;
};

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