910. Smallest Range II
Problem Description
In this problem, you are given an integer array called nums
and an integer k
. Your task is to modify each element in the array by either adding k
to it or subtracting k
from it. After modifying each element in this manner, the score
of the array is defined as the difference between the maximum and minimum elements in the modified array. The objective is to determine the minimum score
that can be achieved by any combination of adding or subtracting k
to/from the elements of nums
.
Here is an example to illustrate:
Suppose nums = [1, 3, 6]
and k = 3
. You could transform nums
as follows:
- Adding
k
to the first element:[1 + 3, 3, 6] = [4, 3, 6]
- Subtracting
k
from the second element:[4, 3 - 3, 6] = [4, 0, 6]
- Subtracting
k
from the third element:[4, 0, 6 - 3] = [4, 0, 3]
The score is then max(4, 0, 3) - min(4, 0, 3) = 4 - 0 = 4
.
The problem is asking you to find the minimum score possible, that is, the smallest difference between the highest and lowest number in the array after each element has been increased or decreased by k
.
Intuition
The intuition behind the solution involves recognizing that sorting the array can help in minimizing the score. By sorting, you can ensure that the operation that you perform (addition or subtraction) will not increase the range unnecessarily.
Here's why sorting helps:
- After sorting
nums
, the smallest and largest elements arenums[0]
andnums[-1]
, respectively. The initial score isnums[-1] - nums[0]
. - Consider a pivot point at index
i
in the sorted array. Everything to the left ofi
could be increased byk
, and everything to the right ofi
(including element ati
) could be decreased byk
. This creates two "blocks" within the array: one with increased values, and one with decreased values. - The new minimum possible value is the minimum of
nums[0] + k
(left-most element of the increased block) andnums[i] - k
(left-most element of the decreased block). - The new maximum possible value is the maximum of
nums[i - 1] + k
(right-most element of the increased block) andnums[-1] - k
(right-most element of the decreased block). - By iterating through all possible pivot points (from
1
tolen(nums) - 1
), you can find the minimum score by comparing this with the previously calculated minimumans
.
The key observation here is that by sorting and choosing an appropriate pivot, one can minimize the difference between the maximum and minimum values affected by the addition or subtraction of k
, leading directly to a solution that iterates through possible pivot points to find the minimum score.
Solution Approach
The solution follows a simple yet effective approach leveraging sorting and iteration.
Algorithm:
-
Sort the
nums
array. This will help us easily identify the smallest and largest elements and ensures that we do not increase the range unnecessarily. -
Initialize the variable
ans
with the initial score, which is the difference between the last element and the first element of the sorted array (nums[-1] - nums[0]
). -
Iterate through the array starting from index
1
up tolen(nums) - 1
. The reason we start at1
is because we are considering the pivot point where the array is divided into two parts: one that will get the addition ofk
and the other the subtraction. There is no point in considering index0
for this pivot as the sorted array's first element cannot be the start of the subtraction section. -
For each index
i
, calculate the minimum and maximum values as follows:-
Calculate the new minimum value
mi
as the minimum betweennums[0] + k
andnums[i] - k
. Thenums[0] + k
represents the smallest possible value after the increment andnums[i] - k
represents the smallest value for the section of the array wherek
is subtracted. -
Calculate the new maximum value
mx
as the maximum betweennums[i - 1] + k
andnums[-1] - k
. Thenums[i - 1] + k
is the largest value of the incremented section, andnums[-1] - k
is the largest value for the decremented section.
-
-
Update the score (
ans
) to be the minimum value between the currentans
and the differencemx - mi
. This ensures that with each iteration, we are considering the lowest possible range after applying our operation at each pivot. -
Once the loop completes,
ans
contains the minimum score achievable after performing the add or subtract operation at each index, based on the givenk
.
Data Structures:
- The sorted array itself is the primary data structure used. No additional data structures are required.
Patterns:
- The use of sorting to establish a predictable order of elements, hence allowing for a methodical approach to finding the solution.
- Iteration to explore possible optimal solutions by checking pivot points in the array.
- Decision-making to update the candidate solution (
ans
) based on comparisons calculated within the loop.
By following these steps, the algorithm ensures that we calculate the minimum range after adding or subtracting k
from each element in the most efficient manner. It elegantly handles the problem by transforming it into a series of operations where we only need to look at the edges of the two blocks created by the pivot point.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through the solution approach with a small example to better illustrate the algorithm.
Suppose we have the following nums
array and integer k
:
1nums = [4, 7, 1] 2k = 5
According to the problem, we have to either add k
to or subtract k
from each element in the array to achieve the smallest possible score (the difference between the maximum and minimum elements of the array). Let's follow the solution approach:
-
Sort the array:
1nums.sort() -> nums = [1, 4, 7]
-
Initialize the score (
ans
):1ans = nums[-1] - nums[0] -> ans = 7 - 1 -> ans = 6
-
Iterate through the array starting from index
1
:For each index
i
, we will calculate the potential new minimum (mi
) and maximum (mx
) values after either adding or subtractingk
:-
At index
i = 1
(element4
):1mi = min(nums[0] + k, nums[i] - k) -> mi = min(1 + 5, 4 - 5) -> mi = min(6, -1) -> mi = -1 2mx = max(nums[i - 1] + k, nums[-1] - k) -> mx = max(1 + 5, 7 - 5) -> mx = max(6, 2) -> mx = 6
Now, we update the
ans
ifmx - mi
is smaller than the currentans
:1ans = min(ans, mx - mi) -> ans = min(6, 6 - (-1)) -> ans = min(6, 7) -> ans = 6
(No change in
ans
as thescore
is still 6 which is not better than the previous score) -
At index
i = 2
(element7
):1mi = min(nums[0] + k, nums[i] - k) -> mi = min(1 + 5, 7 - 5) -> mi = min(6, 2) -> mi = 2 2mx = max(nums[i - 1] + k, nums[-1] - k) -> mx = max(4 + 5, 7 - 5) -> mx = max(9, 2) -> mx = 9
Now, update the
ans
:1ans = min(ans, mx - mi) -> ans = min(6, 9 - 2) -> ans = min(6, 7) -> ans = 6
Again, the
score
is 7, which does not improve theans
.
-
-
Complete the loop: The algorithm has finished checking all possible pivot points in the array.
-
Result: The
ans
calculated is6
, which means:1The minimum score achievable after adding or subtracting `k` from each element in nums is 6.
In this example, the modifications to the elements are unnecessary, as the initial score is already minimal. The algorithm efficiently identifies this by analyzing the potential effects of adding and subtracting k
at each pivot point in the sorted array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def smallestRangeII(self, nums: List[int], k: int) -> int:
5 # First, sort the numbers to organize them in ascending order.
6 nums.sort()
7
8 # The initial range would be the max value minus the min value.
9 smallest_range = nums[-1] - nums[0]
10
11 # Loop through the sorted numbers, starting from the second element,
12 # to find the minimum possible range.
13 for i in range(1, len(nums)):
14 # Calculate the possible minimum by adding k to the smallest value
15 # and subtracting k from the current value.
16 possible_min = min(nums[0] + k, nums[i] - k)
17
18 # Calculate the possible maximum by adding k to the previous value
19 # and subtracting k from the maximum value.
20 possible_max = max(nums[i - 1] + k, nums[-1] - k)
21
22 # Update the smallest range if a smaller one is found.
23 smallest_range = min(smallest_range, possible_max - possible_min)
24
25 # Finally, return the smallest range after considering all elements.
26 return smallest_range
27
1class Solution {
2 public int smallestRangeII(int[] nums, int k) {
3 // First, sort the input array to deal with numbers in a sorted order.
4 Arrays.sort(nums);
5 // Get the length of the array
6 int n = nums.length;
7 // Calculate the initial range from the first and last element of the sorted array.
8 int minRange = nums[n - 1] - nums[0];
9
10 // Iterate through the array starting from the second element
11 for (int i = 1; i < n; ++i) {
12 // Calculate the minimum possible value after adding or subtracting k to the current or first element
13 int currentMin = Math.min(nums[0] + k, nums[i] - k);
14 // Calculate the maximum possible value after adding or subtracting k to the previous or last element
15 int currentMax = Math.max(nums[i - 1] + k, nums[n - 1] - k);
16 // Find the smallest range by comparing the current computed range and the previously stored minimum range
17 minRange = Math.min(minRange, currentMax - currentMin);
18 }
19 // Return the minimum range found
20 return minRange;
21 }
22}
23
1class Solution {
2public:
3 // Defines the function which will find the smallest range after modification
4 int smallestRangeII(vector<int>& nums, int k) {
5 // Initially, sort the array in non-decreasing order
6 sort(nums.begin(), nums.end());
7
8 int numsSize = nums.size(); // Store the size of the nums vector
9 // Compute the initial range between the largest and smallest numbers
10 int minRange = nums[numsSize - 1] - nums[0];
11
12 // Iterate through the sorted numbers starting from the second element
13 for (int i = 1; i < numsSize; ++i) {
14 // Determine the new minimum by comparing the increased smallest number
15 // and the decreased current number
16 int newMin = min(nums[0] + k, nums[i] - k);
17 // Determine the new maximum by comparing the increased previous number
18 // and the decreased largest number
19 int newMax = max(nums[i - 1] + k, nums[numsSize - 1] - k);
20 // Update the minRange with the minimum of the current and new ranges
21 minRange = min(minRange, newMax - newMin);
22 }
23
24 // Return the smallest range found
25 return minRange;
26 }
27};
28
1// Array `nums` holds the numbers and `k` is the allowed modification range
2let nums: number[];
3let k: number;
4
5// Sorts the array in non-decreasing order
6const sortArray = (a: number, b: number) => a - b;
7
8// Finds the smallest range after modification
9function smallestRangeII(nums: number[], k: number): number {
10 // Sort the array in non-decreasing order
11 nums.sort(sortArray);
12
13 // Store the size of the nums array
14 const numsSize: number = nums.length;
15
16 // Compute the initial range between the largest and smallest numbers
17 let minRange: number = nums[numsSize - 1] - nums[0];
18
19 // Iterate through the sorted numbers starting from the second element
20 for (let i = 1; i < numsSize; ++i) {
21 // Determine the new minimum by comparing the increased smallest number and the decreased current number
22 const newMin: number = Math.min(nums[0] + k, nums[i] - k);
23
24 // Determine the new maximum by comparing the increased previous number and the decreased largest number
25 const newMax: number = Math.max(nums[i - 1] + k, nums[numsSize - 1] - k);
26
27 // Update the minRange with the minimum of the current and new ranges
28 minRange = Math.min(minRange, newMax - newMin);
29 }
30
31 // Return the smallest range found
32 return minRange;
33}
34
35// Example usage:
36// nums = [1, 3, 6];
37// k = 3;
38// console.log(smallestRangeII(nums, k)); // Output would be the result of the smallestRangeII function
39
Time and Space Complexity
Time Complexity
The time complexity of the provided code depends on the sorting algorithm and the for loop.
-
nums.sort()
-> The sort operation typically has a time complexity ofO(n log n)
wheren
is the number of elements in the listnums
. -
The for loop -> Iterates through the sorted list once, accounting for a time complexity of
O(n)
.
Combining both, the time complexity remains dominated by the sorting step, and therefore, the overall time complexity is O(n log n)
.
Space Complexity
The space complexity of the provided code is mainly due to the sorted list.
-
nums.sort()
-> The sort operation in Python is usually done in-place, which means the space complexity isO(1)
. -
No additional data structures are used that are dependent on the number of elements in the list, and therefore, no extra space is utilized that is proportional to the input size.
Thus, the space complexity of the code is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.