# Smallest Range II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-range-ii)
Canonical: https://scaleengineer.com/dsa/problems/smallest-range-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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_.

**Example 1:**

**Input:** nums = [1], k = 0
**Output:** 0
**Explanation:** The score is max(nums) - min(nums) = 1 - 1 = 0.

**Example 2:**

**Input:** nums = [0,10], k = 2
**Output:** 6
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Brute Force with Recursion
This approach explores every possible modification of the array. For each element, we have two choices: add `k` or subtract `k`. With `n` elements, this leads to `2^n` possible modified arrays. We generate each one, calculate its score (max - min), and find the minimum score among all possibilities.
**Time:** O(N * 2^N), where N is the number of elements in `nums`. There are `2^N` possible combinations of adding or subtracting `k`. For each combination, we spend O(N) time to find the minimum and maximum values. · **Space:** O(N), where N is the number of elements in `nums`. This is due to the recursion depth and the space needed to store the modified array for each path.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer by exploring all possibilities.
**Cons:** Extremely inefficient due to its exponential nature.; Infeasible for the given constraints where `nums.length` can be up to 10^4.
### Explanation
The core idea is to use a recursive helper function that builds every possible modified array. The function takes the current index `i` and a data structure to hold the modified numbers. At each index `i`, we make two recursive calls: one where `nums[i]` is changed to `nums[i] + k`, and another where `nums[i]` is changed to `nums[i] - k`. The base case for the recursion is when we have processed all elements (i.e., `i == nums.length`). At this point, we have a fully modified array. In the base case, we iterate through the modified array to find its maximum and minimum elements, calculate the score, and update a global minimum score variable. This method is exhaustive but computationally very expensive. ```java class Solution { int minScore = Integer.MAX_VALUE; public int smallestRangeII(int[] nums, int k) { int[] modifiedNums = new int[nums.length]; findMinScore(nums, k, 0, modifiedNums); return minScore; } private void findMinScore(int[] originalNums, int k, int index, int[] modifiedNums) { if (index == originalNums.length) { if (originalNums.length == 0) { minScore = 0; return; } int minVal = modifiedNums[0]; int maxVal = modifiedNums[0]; for (int i = 1; i < modifiedNums.length; i++) { minVal = Math.min(minVal, modifiedNums[i]); maxVal = Math.max(maxVal, modifiedNums[i]); } minScore = Math.min(minScore, maxVal - minVal); return; } modifiedNums[index] = originalNums[index] + k; findMinScore(originalNums, k, index + 1, modifiedNums); modifiedNums[index] = originalNums[index] - k; findMinScore(originalNums, k, index + 1, modifiedNums); } } ```
### Algorithm
* 1. Define a recursive function, say `findMinScore(index, modifiedArray)`. * 2. The base case for the recursion is when `index` reaches the end of the array. * 3. In the base case, calculate the difference between the maximum and minimum elements of `modifiedArray` and update the global minimum score. * 4. For the recursive step at `index`: * a. Make a recursive call for the case where the element at `index` is `nums[index] + k`. * b. Make another recursive call for the case where the element at `index` is `nums[index] - k`. * 5. Initialize the process by calling the function with `index = 0`.

## Greedy Approach with Sorting
A much more efficient approach involves sorting the array first. The key insight is that to minimize the range (max - min), we should try to increase the smaller numbers and decrease the larger numbers. After sorting, any optimal solution will involve adding `k` to a prefix of the array and subtracting `k` from the remaining suffix.
**Time:** O(N log N), where N is the number of elements. The sorting step dominates the complexity. The subsequent loop runs N-1 times with constant time operations. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
**Pros:** Highly efficient and passes for the given constraints.; Based on a clever greedy insight that simplifies the problem from exponential to polynomial time.
**Cons:** Requires sorting, which might not be ideal if the array is frequently updated.; The logic is less intuitive than the brute-force approach and requires a proof of correctness.
### Explanation
Let's sort the input array `nums`. After sorting, let the elements be `nums[0], nums[1], ..., nums[n-1]`. The initial score can be `nums[n-1] - nums[0]`. This corresponds to a scenario where we either add `k` to all elements or subtract `k` from all elements, which doesn't change the score. This serves as our initial upper bound for the minimum score. The core idea is that for an optimal arrangement, there must be a split point `i` such that all elements `nums[0]...nums[i]` are increased by `k`, and all elements `nums[i+1]...nums[n-1]` are decreased by `k`. This is because if we had `nums[j] - k` and `nums[l] + k` for some `j < l`, we could swap the operations to `nums[j] + k` and `nums[l] - k`. This swap would not increase the overall range and might decrease it, suggesting the partitioned structure is optimal. We can iterate through all possible split points `i` from `0` to `n-2`. For each split point `i`, the new maximum element will be `max(nums[i] + k, nums[n-1] - k)` and the new minimum element will be `min(nums[0] + k, nums[i+1] - k)`. We calculate the score for this split and update our overall minimum score. After checking all possible splits, the minimum score found is the answer. ```java import java.util.Arrays; class Solution { public int smallestRangeII(int[] nums, int k) { int n = nums.length; if (n <= 1) { return 0; } Arrays.sort(nums); int minScore = nums[n - 1] - nums[0]; for (int i = 0; i < n - 1; i++) { int high = Math.max(nums[i] + k, nums[n - 1] - k); int low = Math.min(nums[0] + k, nums[i + 1] - k); minScore = Math.min(minScore, high - low); } return minScore; } } ```
### Algorithm
* 1. Get the length of the array, `n`. If `n <= 1`, return 0. * 2. Sort the array `nums` in non-decreasing order. * 3. Initialize a variable `minScore` with the initial range `nums[n-1] - nums[0]`. * 4. Iterate with an index `i` from `0` to `n-2`. This `i` represents the last index of the prefix that gets `+k`. * 5. Inside the loop, for each `i`: * a. Calculate the potential maximum of the new array: `high = max(nums[i] + k, nums[n-1] - k)`. * b. Calculate the potential minimum of the new array: `low = min(nums[0] + k, nums[i+1] - k)`. * c. Update the result: `minScore = min(minScore, high - low)`. * 6. After the loop, return `minScore`.

# Solutions
### Java

```java
class Solution {
public
  int smallestRangeII(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length;
    int ans = nums[n - 1] - nums[0];
    for (int i = 1; i < n; ++i) {
      int mi = Math.min(nums[0] + k, nums[i] - k);
      int mx = Math.max(nums[i - 1] + k, nums[n - 1] - k);
      ans = Math.min(ans, mx - mi);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int smallestRangeII(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int ans = nums[n - 1] - nums[0];
    for (int i = 1; i < n; ++i) {
      int mi = min(nums[0] + k, nums[i] - k);
      int mx = max(nums[i - 1] + k, nums[n - 1] - k);
      ans = min(ans, mx - mi);
    }
    return ans;
  }
};

```

### Python

```python
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

```