Skip to main content

Smallest Range II

Problem Description

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.

Examples

Example 1:

Input
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.

Constraints

  • 1nums.length1041 \leq nums.length \leq 104
  • 0nums[i]1040 \leq nums[i] \leq 104
  • 0k1040 \leq k \leq 104

Solution for Smallest Range II

Approach: Linear Scan

Intuition

As in Smallest Range I, smaller A[i] will choose to increase their value ("go up"), and bigger A[i] will decrease their value ("go down").

Algorithm

We can formalize the above concept: if A[i] < A[j], we don't need to consider when A[i] goes down while A[j] goes up. This is because the interval (A[i] + K, A[j] - K) is a subset of (A[i] - K, A[j] + K) (here, (a, b) for a > b denotes (b, a) instead.)

That means that it is never worse to choose (up, down) instead of (down, up). We can prove this claim that one interval is a subset of another, by showing both A[i] + K and A[j] - K are between A[i] - K and A[j] + K.

For sorted A, say A[i] is the largest i that goes up. Then A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K are the only relevant values for calculating the answer: every other value is between one of these extremal values.

Code in Different Languages

Written by @Shreyash3087
class Solution {
public:
int smallestRangeII(vector<int>& A, int K) {
int N = A.size();
sort(A.begin(), A.end());
int ans = A[N-1] - A[0];

for (int i = 0; i < A.size() - 1; ++i) {
int a = A[i], b = A[i+1];
int high = max(A[N-1] - K, a + K);
int low = min(A[0] + K, b - K);
ans = min(ans, high - low);
}
return ans;
}
};

Complexity Analysis

Time Complexity: O(NlogN)O(NlogN)

Reason: where N is the length of the A.

Space Complexity: O(N)O(N) or O(logN)O(logN)

Reason:

  • The space complexity of the sorting algorithm depends on the implementation of each programming language.

  • For instance, the list.sort() function in Python is implemented with the Timsort algorithm whose space complexity is O(N)O(N).

  • In Java, the Arrays.sort() is implemented as a variant of quicksort algorithm whose space complexity is O(logN)O(log⁡N).

Video Solution

References


Authors:

Loading...