# Smallest Range I
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-range-i)
Canonical: https://scaleengineer.com/dsa/problems/smallest-range-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and an integer `k`.

In one operation, you can choose any index `i` where `0 <= i < nums.length` and change `nums[i]` to `nums[i] + x` where `x` is an integer from the range `[-k, k]`. You can apply this operation **at most once** for each index `i`.

The **score** of `nums` is the difference between the maximum and minimum elements in `nums`.

Return _the minimum **score** of_ `nums` _after applying the mentioned operation at most once for each index in it_.

**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:** 0
**Explanation:** Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

**Constraints:**

* `1 <= nums.length <= 104`
* `0 <= nums[i] <= 104`
* `0 <= k <= 104`

# Approaches
## Sorting Approach
This approach involves sorting the array first to easily find the minimum and maximum elements. Once the array is sorted, the minimum element is the first element and the maximum is the last. With these values, we can calculate the smallest possible range.
**Time:** O(N log N), where N is the number of elements in `nums`. This is because sorting the array takes O(N log N) time, which dominates the other constant-time operations. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used by the language's standard library. For example, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Simple to understand and implement.; Correctly identifies the minimum and maximum values needed for the calculation.
**Cons:** The sorting step is unnecessary and makes the algorithm less efficient than it could be.; Time complexity is dominated by the sort, which is not optimal for this problem.
### Explanation
The core idea is that to minimize the difference `max(nums) - min(nums)`, we should aim to increase the minimum value and decrease the maximum value. The maximum possible value for the new minimum is `original_min + k`. The minimum possible value for the new maximum is `original_max - k`. By sorting the array `nums`, we can find the original minimum (`nums[0]`) and maximum (`nums[nums.length - 1]`) in O(1) time after the sort. The potential new range would be `(original_max - k) - (original_min + k)`, which simplifies to `original_max - original_min - 2k`. If this difference is negative, it means the range `[original_max - k, original_min + k]` is overlapping. This implies we can make all elements equal to some value within this overlap, resulting in a score of 0. Therefore, the smallest possible score is `max(0, (nums[nums.length - 1] - nums[0]) - 2 * k)`. The algorithm is as follows:
### Algorithm
- Handle the edge case where the array has only one element. In this case, the range is always 0.
- Sort the input array `nums` in non-decreasing order.
- Identify the minimum value as `min_val = nums[0]`.
- Identify the maximum value as `max_val = nums[nums.length - 1]`.
- Calculate the initial difference: `diff = max_val - min_val`.
- If `diff <= 2 * k`, it's possible to make all elements equal, so the minimum score is 0. Return 0.
- Otherwise, the minimum score is `diff - 2 * k`. Return this value.
- This can be concisely written as `return Math.max(0, max_val - min_val - 2 * k);`

```java
import java.util.Arrays;

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        if (nums.length == 1) {
            return 0;
        }
        Arrays.sort(nums);
        int minVal = nums[0];
        int maxVal = nums[nums.length - 1];
        int diff = maxVal - minVal;
        return Math.max(0, diff - 2 * k);
    }
}
```

## Single Pass Approach
A more efficient approach avoids sorting by finding the minimum and maximum elements in a single pass through the array. This reduces the time complexity from O(N log N) to O(N).
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the array once to find the minimum and maximum values. · **Space:** O(1), as we only use a constant amount of extra space for variables like `minVal` and `maxVal`.
**Pros:** Optimal time complexity as it requires only one pass through the array.; Minimal space usage (O(1)).; Simple and efficient.
**Cons:** No significant cons for this problem as it is optimal.
### Explanation
The logic remains the same as the sorting approach: the goal is to minimize the range by increasing the smallest element and decreasing the largest element. The key insight is that we only need the original minimum and maximum values, not the entire sorted array. We can find these two values by iterating through the array just once. We initialize two variables, `min_val` and `max_val`, with the value of the first element. During the iteration, we update `min_val` and `max_val` whenever we encounter a smaller or larger element, respectively. After the single pass, we have the required `min_val` and `max_val`. The final calculation is identical to the previous approach: `max(0, max_val - min_val - 2 * k)`. The algorithm is as follows:
### Algorithm
- Handle the edge case where the array has only one element, returning 0.
- Initialize `min_val` to `nums[0]` and `max_val` to `nums[0]`.
- Iterate through the array `nums` from the second element.
- In each iteration, update the minimum: `min_val = Math.min(min_val, nums[i])`.
- In each iteration, update the maximum: `max_val = Math.max(max_val, nums[i])`.
- After the loop finishes, calculate the result: `result = max_val - min_val - 2 * k`.
- Since the score cannot be negative, return `Math.max(0, result)`.

```java
class Solution {
    public int smallestRangeI(int[] nums, int k) {
        if (nums.length == 1) {
            return 0;
        }
        int minVal = nums[0];
        int maxVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            minVal = Math.min(minVal, nums[i]);
            maxVal = Math.max(maxVal, nums[i]);
        }
        int diff = maxVal - minVal;
        return Math.max(0, diff - 2 * k);
    }
}
```

# Solutions
### Java

```java
class Solution { public int smallestRangeI ( int [] nums , int k ) { int mx = 0 ; int mi = 10000 ; for ( int v : nums ) { mx = Math . max ( mx , v ); mi = Math . min ( mi , v ); } return Math . max ( 0 , mx - mi - k * 2 ); } }
```

### CPP

```cpp
class Solution { public: int smallestRangeI ( vector < int >& nums , int k ) { auto [ mi , mx ] = minmax_element ( nums . begin (), nums . end ()); return max ( 0 , * mx - * mi - k * 2 ); } };
```

### Python

```python
class Solution : def smallestRangeI ( self , nums : List [ int ], k : int ) -> int : mx , mi = max ( nums ), min ( nums ) return max ( 0 , mx - mi - k * 2 )
```