Leetcode 908. Smallest Range I

Problem Explanation

The problem is asking to determine the smallest possible difference between the maximum and minimum values of an array after adding or subtracting a number K to each element of the array.

We're given an array, A of size n where each element, A[i] represents an integer number. We're also given an integer K where -K <= x <= K. The process involves choosing an integer x within the range -K to K inclusive and adding x to each element in the array.

The goal is to find and return the smallest possible difference between the largest (max) and smallest (min) elements of the array after the operation.

The solution to this problem is to find the current maximum and minimum values of the array. This difference is the maximum possible difference. From this maximum difference, deduct double the value of K. If the result of this operation is negative, return 0. Otherwise, return the result. The reason for deducting double K is because we can add K to the minimum value and subtract K from the maximum value, effectively reducing the difference by 2K.

Example Walkthrough

Let's consider an example to illustrate this:

Suppose A = [0,10] and K = 2.

The max of A is 10 and the min of A is 0, so the maximum possible difference is 10 - 0 = 10.

Then we subtract 2K (in this case, 2*2 = 4) from the maximum possible difference: 10 - 4 = 6.

So the result is 6.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int smallestRangeI(vector<int>& nums, int k) {
6    // Find the maximum and minimum elements in the nums vector
7    const int max = *max_element(begin(nums), end(nums));
8    const int min = *min_element(begin(nums), end(nums));
9
10    // Return max difference after subtracting 2k or 0 if the difference is negative
11    return std::max(0, max - min - 2 * k);
12  }
13};

Python Solution

1
2python
3class Solution:
4    def smallestRangeI(self, nums, K):
5        # Find the maximum and minimum elements in the nums list
6        max_num = max(nums)
7        min_num = min(nums)
8        
9        # Return max difference after subtracting 2k or 0 if the difference is negative
10        return max(0, max_num - min_num - 2 * K)

Java Solution

1
2java
3import java.util.Arrays;
4
5class Solution {
6    public int smallestRangeI(int[] nums, int K) {
7        // Find the maximum and minimum elements in the nums array
8        int max = Arrays.stream(nums).max().getAsInt();
9        int min = Arrays.stream(nums).min().getAsInt();
10
11        // Return max difference after subtracting 2k or 0 if the difference is negative
12        return Math.max(0, max - min - 2 * K);
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4  smallestRangeI(nums, K) {
5    // Find the maximum and minimum elements in the nums array
6    let max = Math.max(...nums);
7    let min = Math.min(...nums);
8
9    // Return max difference after subtracting 2k or 0 if the difference is negative
10    return Math.max(0, max - min - 2 * K);
11  }
12}

C# Solution

1
2csharp
3using System;
4using System.Linq;
5
6public class Solution {
7    public int SmallestRangeI(int[] nums, int K) {
8        // Find the maximum and minimum elements in the nums array
9        int max = nums.Max();
10        int min = nums.Min();
11
12        // Return max difference after subtracting 2k or 0 if the difference is negative
13        return Math.Max(0, max - min - 2 * K);
14    }
15}

R Solution

1
2R
3smallest_range <- function(nums, k) {
4  # Find the maximum and minimum elements in the nums list
5  max_num <- max(nums)
6  min_num <- min(nums)
7
8  # Return max difference after subtracting 2k or 0 if the difference is negative
9  return(pmax(0, max_num - min_num - 2 * k))
10}

Ruby Solution

1
2ruby
3class Solution
4  def smallest_range(nums, k)
5    # Find the maximum and minimum elements in the nums array
6    max_num = nums.max
7    min_num = nums.min
8
9    # Return max difference after subtracting 2k or 0 if the difference is negative
10    [0, max_num - min_num - 2 * k].max
11  end
12end

Conclusion

In this article, we analyzed a problem of minimizing the difference between the highest and lowest values in an array by adding or subtracting a value to each element in the array. We took a walk through an example and provided solutions in seven different programming languages: C++, Python, Java, JavaScript, C#, R and Ruby. The same core logic applies across all implementations, making it a classic problem with multi-language solutions. This problem hones your problem-solving skills and gives you exposure to language-specific functions and methods like min, max, etc. It also shows you that although syntax may differ, the logic behind programming problems remains the same across different languages.


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 👨‍🏫