This problem asks to minimize the score defined as the difference between the maximum and minimum elements after modifying each number by either adding or subtracting k. A greedy approach with sorting identifies the optimal boundary adjustments. By evaluating splits between lower and upper partitions, you compute the smallest achievable range efficiently in O(N log N) time.
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.
How GhostInterview Helps
- Identifies the optimal greedy split points automatically and tracks minimal scores without manual trial.
- Ensures boundary conditions are correctly evaluated, avoiding common off-by-one or edge-case errors.
- Generates step-by-step explanations for each partition, linking array positions to their final adjusted values.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Smallest Range II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Smallest Range II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given an integer array, find the largest perimeter of a triangle formed from three of these lengths.
Open problem page#1363 Largest Multiple of ThreeFind the largest number divisible by three by selecting and ordering digits optimally using state transition dynamic programming techniques.
Open problem page#1561 Maximum Number of Coins You Can GetSolve the Maximum Number of Coins You Can Get using greedy pile selection and invariant validation to maximize your coins efficiently.
Open problem page