908. Smallest Range I

EasyArrayMath
Leetcode Link

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:

  1. 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.
  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

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:

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

    1mx, mi = max(nums), min(nums)

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

    1adjusted_range = mx - mi - k * 2

  3. 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).

    1minimum_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).

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

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

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

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

  1. Find Maximum and Minimum Values:

    • Maximum value mx in the array is 6.
    • Minimum value mi in the array is 1.

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

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

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Math Basics

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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫