#910

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Smallest Range II

Determine the minimum possible difference between the largest and smallest numbers after adjusting each by plus or minus k optimally.

array math greedy sorting

Problem Statement

Given an integer array nums and an integer k, you may modify each nums[i] by either adding k or subtracting k. Determine the minimal possible score after all modifications, where the score is the difference between the maximum and minimum elements in the modified array.

Constraints include that nums contains at least 1 element and at most 10,000 elements, each element is between 0 and 10,000, and k is between 0 and 10,000. Optimize the approach to handle large arrays while maintaining correctness with greedy selection and boundary validation.

Examples

Example 1

Input: nums = [1], k = 0

Output: 0

The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2

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

Output: 6

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

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

Solution Approach

Sort the array

Begin by sorting nums to simplify evaluating potential minimum and maximum values after modification. Sorting allows you to define the lower and upper partitions efficiently and ensures the greedy strategy can check split points correctly.

Compute initial range

Calculate the original range as max(nums) - min(nums). Then iterate over the array, considering the effect of adding k to the left side and subtracting k from the right side at each split. Track the minimal score found across all splits.

Evaluate greedy splits

For each index i, treat nums[0..i] as increased by k and nums[i+1..n-1] as decreased by k. Update the score using max of (last element minus k, first element plus k) minus min of (first element plus k, last element minus k). Keep the lowest result across all i.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	Depends on the final approach

Sorting takes O(N log N) time, and evaluating splits is O(N). Space complexity depends on whether a new sorted array is used; in-place sorting keeps it O(1), otherwise O(N).

What Interviewers Usually Probe

Sorting is often expected before evaluating greedy splits in range minimization problems.
Interviewer may ask why both adding and subtracting k must be considered for each element to avoid missing smaller ranges.
Clarify the correctness by explaining why boundary elements dominate the maximum and minimum after partitioning.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort before attempting greedy splits can lead to incorrect minimal ranges.
Neglecting edge cases where k = 0 or all elements are equal may yield incorrect outputs.
Confusing which side of the split should be incremented or decremented breaks the invariant logic.

Follow-up variants

Smallest Range I, where only adding or subtracting k uniformly is allowed.
Maximize minimum value after ±k adjustments instead of minimizing the range.
Handling negative numbers in nums while maintaining the greedy split strategy.

FAQ

What is the key strategy for Smallest Range II?

The key is a greedy approach after sorting, evaluating each split by adding k to one side and subtracting k from the other.

Why do I need to consider both +k and -k for each number?

Considering both ensures all possible minimal ranges are checked; missing one choice can yield a suboptimal result.

Can this solution handle arrays with 10,000 elements efficiently?

Yes, sorting is O(N log N) and the split evaluation is O(N), making it feasible for large arrays.

How do edge cases like k = 0 affect the solution?

When k = 0, the array is unmodified, so the minimal range is simply max(nums) - min(nums).

Does this greedy approach always find the true minimum range?

Yes, because the optimal configuration occurs at a split point after sorting, considering both +k and -k choices for partitions.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = nums[-1] - nums[0]
        for i in range(1, len(nums)):
            mi = min(nums[0] + k, nums[i] - k)
            mx = max(nums[i - 1] + k, nums[-1] - k)
            ans = min(ans, mx - mi)
        return ans

Continue Practicing

#976 largest perimeter triangle #1363 largest multiple of three #1561 maximum number of coins you can get