Smallest Range II - Practice Coding Problems

Smallest Range II - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,6], k = 3

› Output: 3

💡 Note: After changes: [1+3, 3+3, 6-3] = [4,6,3]. Range = max(4,6,3) - min(4,6,3) = 6-3 = 3

Example 2 — All Same Operation

$ Input: nums = [0,10], k = 2

› Output: 6

💡 Note: Best choice: [0+2, 10-2] = [2,8]. Range = 8-2 = 6. (Better than [2,12] range=10 or [-2,8] range=10)

Example 3 — Single Element

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

› Output: 0

💡 Note: Only one element, so range is always 0 regardless of operations

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,6] with k=3, current range = 5

Transform

Each element can become nums[i]+k or nums[i]-k

Optimize

Find assignment that minimizes max-min

Key Takeaway

🎯 Key Insight: Sort first, then find the optimal split point where prefix adds k and suffix subtracts k

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is that after sorting, the optimal solution has a prefix-suffix structure where elements before some split point add k and elements after subtract k. The greedy approach sorts the array and tries all possible split points in O(n log n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Try all 2^n combinations of adding/subtracting k
Sort and Split Strategy	O(n log n)	O(1)	Sort array, then find optimal split point between +k and -k groups
Greedy Optimization	O(n log n)	O(1)	Make locally optimal choices to minimize the range

Brute Force - Try All Combinations — Algorithm Steps

Generate all 2^n combinations of +k/-k operations
Calculate max-min for each combination
Return the minimum range found

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Array [1,3,6] with k=3

Generate

Try all 2³=8 combinations of +3/-3

Result

Find combination with minimum range

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int k) {
    int minRange = INT_MAX;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        int* arr = (int*)malloc(numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                arr[i] = nums[i] + k;
            } else {
                arr[i] = nums[i] - k;
            }
        }
        
        int maxVal = arr[0], minVal = arr[0];
        for (int i = 1; i < numsSize; i++) {
            if (arr[i] > maxVal) maxVal = arr[i];
            if (arr[i] < minVal) minVal = arr[i];
        }
        
        int currentRange = maxVal - minVal;
        if (currentRange < minRange) {
            minRange = currentRange;
        }
        
        free(arr);
    }
    
    return minRange;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n combinations, each takes O(n) to compute min/max

✓ Linear Growth

Space Complexity

O(n)

Array to store current combination

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

867 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler