908. Smallest Range I

Problem Description

In this problem, we are given an array of integers, nums, and an integer k. Our goal is to minimize the score of nums, defined as the difference between the maximum and minimum elements in the array.

We have the ability to perform an operation on each element of the array. The operation involves choosing an index i and then changing the value of nums[i] by adding an integer x that can range from -k to k (inclusive). We are allowed to use this operation at most once for each index.

The objective is to determine what the minimum achievable score is after applying the operation no more than once to each element of the array, if at all.

Intuition

The intuition behind the solution comes from understanding how the score is calculated—the score is simply the difference between the largest and smallest numbers in the array. If we increase the smaller numbers and/or decrease the larger numbers, we can bring them closer to each other, thus reducing the score.

Since we can only apply the operation once per index, our best strategy is to reduce the maximum possible value by k and to increase the minimum possible value by k. By doing so, we reduce or eliminate the gap between the maximum and minimum values as much as possible.

The solution checks two scenarios:

If the original maximum value minus the minimum value is less than or equal to 2 * k, then we can fully bridge the gap, making the score zero.
If the gap is larger than 2 * k, we do our best by reducing the gap by 2 * k (subtracting k from the maximum value and adding k to the minimum value) and the remaining difference is the minimal score possible.

Therefore, the formula max(0, mx - mi - k * 2) is used, where mx and mi are the maximum and minimum values in the array, respectively. We use max(0, ...) because the score cannot be negative—if the max-min difference is less than or equal to double of k, bridging the gap completely, the score would be zero.

Learn more about Math patterns.

Solution Approach

The solution to this problem is quite straightforward, without involving complex algorithms or data structures. It follows a direct mathematical approach that efficiently arrives at the result.

Here's a breakdown of the solution implementation:

Find Maximum and Minimum Values: We start by finding the maximum (mx) and minimum (mi) values in the array nums. This can be done efficiently in a linear pass over the array.
```
mx, mi = max(nums), min(nums)
```
Calculate Adjusted Range: We then calculate what the new range (difference between maximum and minimum) would be if we were to reduce the maximum value by k and increase the minimum value by k.
```
adjusted_range = mx - mi - k * 2
```
Determine the Minimum Score: Finally, we evaluate the minimum score, which would be the adjusted range if it's positive, or 0 if the adjusted range is negative (which means the entire range has been neutralized by the operation).
```
minimum_score = max(0, adjusted_range)
```
The use of max(0, ...) ensures that our final score is not negative, adhering to the definition that the score is the difference between two values (which is inherently non-negative).
Return the Result: The calculated minimum_score is returned as the final result.

This approach uses constant extra space and has a time complexity of O(N) due to the need to iterate over the array to find the minimum and maximum values. No additional patterns or complex operations are needed, making this an efficient and clean solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an array [1, 3, 6] as a small example to illustrate the solution approach, with k = 3.

Find Maximum and Minimum Values:
- Maximum value mx in the array is 6.
- Minimum value mi in the array is 1.
Calculate Adjusted Range:
- We can reduce the maximum value (mx) by k (6 - 3 = 3) and increase the minimum value (mi) by k (1 + 3 = 4).
- The new adjusted range would be the new maximum value (3) minus the new minimum value (4), which is 3 - 4 = -1.
- However, since we cannot have a negative score, we consider the adjusted range as 0.
Determine the Minimum Score:
- The minimum score is the maximum between 0 and the adjusted range.
- Since in our example the adjusted range is -1, we use 0 because the score can't be negative.
- Therefore, the minimum score is 0.
Return the Result:
- With the given nums array [1, 3, 6] and k = 3, the minimum achievable score after applying the operations is 0.

In this case, we can conclude that after applying +k to the minimum value and -k to the maximum value, the adjusted values end up overlapping, and the minimum score becomes zero, which is the best-case scenario.

Solution Implementation

1# Import the typing module to use the List type hint
2from typing import List
3
4class Solution:
5    def smallestRangeI(self, nums: List[int], k: int) -> int:
6        # Find the maximum and minimum values in the list of numbers
7        max_num, min_num = max(nums), min(nums)
8      
9        # Calculate the possible smallest range after performing the operation
10        # described in the problem statement, which reduces the difference
11        # between the maximum and minimum numbers by 2*k (k from the max and
12        # k from the min). If the difference is already less than 2*k,
13        # the smallest range can be brought down to 0.
14        smallest_range = max(0, max_num - min_num - 2 * k)
15      
16        # Return the calculated smallest range
17        return smallest_range
18

1class Solution {
2    public int smallestRangeI(int[] nums, int k) {
3        // Initialize maximum and minimum values to be the opposite of their extremes.
4        // This ensures that they will be replaced by actual array values.
5        int maxNum = nums[0]; // Initially set maxNum to the first element.
6        int minNum = nums[0]; // Initially set minNum to the first element.
7
8        // Iterate through the array to find the maximum and minimum values.
9        for (int value : nums) {
10            maxNum = Math.max(maxNum, value); // Update maxNum if current value is greater.
11            minNum = Math.min(minNum, value); // Update minNum if current value is smaller.
12        }
13
14        // Calculate the maximum achievable difference by subtracting the range extension
15        // from the actual range. Ensure the result is not negative.
16        // The range extension is 'k' from both sides of the range, hence 'k * 2'.
17        int maxDiff = Math.max(0, maxNum - minNum - k * 2);
18
19        // Return the smallest possible range after the operations.
20        return maxDiff;
21    }
22}
23

1#include <vector>
2#include <algorithm> // For std::max_element and std::min_element
3
4class Solution {
5public:
6    // This function finds the smallest possible range after adding/subtracting
7    // a value k to each element in the array
8    int smallestRangeI(vector<int>& nums, int k) {
9        // Find the maximum value in the array using std::max_element
10        int maxVal = *std::max_element(nums.begin(), nums.end());
11      
12        // Find the minimum value in the array using std::min_element
13        int minVal = *std::min_element(nums.begin(), nums.end());
14      
15        // Calculate the adjusted range after adding/subtracting k
16        // The range cannot be negative, hence the use of std::max with 0
17        return std::max(0, maxVal - minVal - 2 * k);
18    }
19};
20

1function smallestRangeI(nums: number[], k: number): number {
2    // Find the maximum value in the array using reduce method.
3    const maxValue = nums.reduce((currentMax, value) => Math.max(currentMax, value), -Infinity);
4
5    // Find the minimum value in the array using reduce method.
6    const minValue = nums.reduce((currentMin, value) => Math.min(currentMin, value), Infinity);
7
8    // Calculate the adjusted range after the operation, ensuring it can't be less than 0.
9    // The operation allows for increasing and decreasing each element by up to k.
10    // The goal is to find the smallest possible range [minValue+k, maxValue-k]
11    // then we calculate the difference between the maximum and minimum of that range
12    // if it is less than 0, we return 0 as the range cannot be negative.
13    return Math.max(maxValue - minValue - k * 2, 0);
14}
15

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the number of elements in the given nums list. This is because the function uses the max and min functions which each need to iterate over all elements of the list once to determine the maximum and minimum values, respectively.

Space Complexity

The space complexity of the code is O(1) as the memory usage is constant and does not depend on the input size N. Only a fixed number of variables (mx, mi, and the return value) are used, which occupy a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know