Jobs

Interviews

Discussions

Smallest Range II

Medium

Asked by:

31 views

Topics:

Arrays

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.

Example 1:

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.

Example 3:

Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

Try coding it in LeetCode

Smallest Range II

Medium

Asked by:

31 views

Topics:

Arrays

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.

Example 1:

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.

Example 3:

Input: nums = [1,3,6], k = 3
Output: 3
Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁴
0 <= k <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the input array `nums`, and for the integer `k`?
Can the input array `nums` be empty or null?
Are all the numbers in the input array integers?
If the array `nums` contains only one element, what should the function return?
If multiple possible choices of adding or subtracting k from each number result in the same smallest range, is any one of those acceptable?

Brute Force Solution

Approach

The brute force strategy for this problem involves trying every single possible combination of adding or subtracting a certain value from each number in the list. Then we calculate the difference between the biggest and smallest number of this new transformed list. The smallest difference we find after trying all possible combinations is the answer.

Here's how the algorithm would work step-by-step:

For each number in the list, we have two options: either add a certain value to it or subtract that same value from it.
We consider every possible combination of these choices. For example, we might add to the first number and subtract from the rest, or add to all of them, or subtract from all of them, and so on.
For each of these combinations, we find the biggest and smallest numbers in the list after adding or subtracting.
We then calculate the difference between the biggest and smallest numbers.
We keep track of the smallest difference we find across all the combinations we try.
Finally, the smallest difference we kept track of is our answer.

Code Implementation

def smallest_range_brute_force(numbers, some_value):
    list_length = len(numbers)
    smallest_range = float('inf')

    # Iterate through all possible combinations of adding/subtracting
    for i in range(2**list_length):
        modified_numbers = []

        # Build the current combination of added/subtracted numbers
        for j in range(list_length):
            if (i >> j) & 1:
                modified_numbers.append(numbers[j] + some_value)
            else:
                modified_numbers.append(numbers[j] - some_value)

        # Find max and min of the modified array
        maximum_value = max(modified_numbers)

        minimum_value = min(modified_numbers)

        # Update smallest range if needed
        smallest_range = min(smallest_range, maximum_value - minimum_value)

    return smallest_range

Big(O) Analysis

Time Complexity

O(2^n) – The core of the algorithm involves exploring all possible combinations of adding or subtracting a value from each number in the input list. Since each of the 'n' numbers has two choices (add or subtract), the total number of combinations to explore is 2*2*...*2 (n times), which equals 2^n. For each of these 2^n combinations, we need to find the maximum and minimum values in the modified list, which takes O(n) time. However, the dominant factor is the enumeration of combinations. Therefore, the overall time complexity is O(2^n * n), but since the 2^n term grows much faster than n, we can simplify it to O(2^n).

Space Complexity

O(1) – The brute force approach described involves iterating through every possible combination of adding or subtracting a value from each number in the input list. Although it considers all combinations, it does not explicitly store all of these combinations in a new data structure. It only calculates the range (max - min) for each combination and keeps track of the smallest range found so far. This process requires a constant amount of extra space to store the current range, the minimum range found, and potentially some loop counters or index variables, irrespective of the input size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to minimize the difference between the largest and smallest numbers in a set, after either adding or subtracting a fixed value from each number. The best approach involves sorting the numbers and then focusing on how adding/subtracting changes the potential maximum and minimum values.

Here's how the algorithm would work step-by-step:

First, arrange the numbers in increasing order.
Consider that the sorted numbers will be either increased or decreased by a fixed amount. Focus on the point where the numbers transition from being decreased to being increased.
Imagine a 'pivot' point within the sorted set. All numbers before the pivot will be increased, and all numbers after the pivot will be decreased.
For each possible pivot point, calculate the potential new maximum and minimum values after applying the increase/decrease.
The potential new maximum will be either the largest original number decreased, or the number right before the pivot increased.
The potential new minimum will be either the smallest original number increased, or the number right after the pivot decreased.
Calculate the difference between the potential maximum and minimum for each pivot choice.
Find the smallest difference among all these pivot choices. This is the smallest possible range.

Code Implementation

def smallest_range_two(numbers, add_subtract_value):
    numbers.sort()
    array_length = len(numbers)
    initial_difference = numbers[-1] - numbers[0]
    smallest_range = initial_difference

    for i in range(array_length - 1):
        # Consider each element as a potential pivot
        potential_maximum = max(numbers[-1] - add_subtract_value, numbers[i] + add_subtract_value)

        # Determine the potential minimum value
        potential_minimum = min(numbers[0] + add_subtract_value, numbers[i+1] - add_subtract_value)

        smallest_range = min(smallest_range, potential_maximum - potential_minimum)

    return smallest_range

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the input array of size n, which takes O(n log n) time. After sorting, the algorithm iterates through the array once to consider each element as a potential pivot point. The loop takes O(n) time. However, since the sorting step dominates the runtime, the overall time complexity is O(n log n) + O(n), which simplifies to O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in-place which does not contribute to auxiliary space. We only use a few constant space variables like the pivot point, potential maximum, and potential minimum during the iteration. The space used by these variables does not scale with the input size N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is null or empty, as no range can be calculated.
Single element array	Return 0 since the range is zero if there is only one element.
Array with two identical elements and K=0	Return 0 since the range remains 0 after potentially adding/subtracting 0.
Array with two identical elements and large K	Handle the K value correctly to ensure the minimum difference between the altered identical elements are calculated correctly by either adding K to the smaller and subtracting K to the larger or vice versa.
Array with all identical values	The range will always be zero regardless of K's value; handle addition/subtraction of K correctly.
K is zero	Return the original range (max - min) as no change occurs.
Large input array with large values and large K	Ensure that integer overflow does not occur during calculations by using long data type.
Array is already sorted or reverse sorted	The algorithm should correctly adjust the values regardless of the initial order of the array.

Empty or null input array

How to Handle:

Return 0 if the input array is null or empty, as no range can be calculated.

Single element array

How to Handle:

Return 0 since the range is zero if there is only one element.

Array with two identical elements and K=0

How to Handle:

Return 0 since the range remains 0 after potentially adding/subtracting 0.

Array with two identical elements and large K

How to Handle:

Handle the K value correctly to ensure the minimum difference between the altered identical elements are calculated correctly by either adding K to the smaller and subtracting K to the larger or vice versa.

Array with all identical values

How to Handle:

The range will always be zero regardless of K's value; handle addition/subtraction of K correctly.

K is zero

How to Handle:

Return the original range (max - min) as no change occurs.

Large input array with large values and large K

How to Handle:

Ensure that integer overflow does not occur during calculations by using long data type.

Array is already sorted or reverse sorted

How to Handle:

The algorithm should correctly adjust the values regardless of the initial order of the array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the input array `nums`, and for the integer `k`?
Can the input array `nums` be empty or null?
Are all the numbers in the input array integers?
If the array `nums` contains only one element, what should the function return?
If multiple possible choices of adding or subtracting k from each number result in the same smallest range, is any one of those acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each number in the list, we have two options: either add a certain value to it or subtract that same value from it.
We consider every possible combination of these choices. For example, we might add to the first number and subtract from the rest, or add to all of them, or subtract from all of them, and so on.
For each of these combinations, we find the biggest and smallest numbers in the list after adding or subtracting.
We then calculate the difference between the biggest and smallest numbers.
We keep track of the smallest difference we find across all the combinations we try.
Finally, the smallest difference we kept track of is our answer.

Code Implementation

def smallest_range_brute_force(numbers, some_value):
    list_length = len(numbers)
    smallest_range = float('inf')

    # Iterate through all possible combinations of adding/subtracting
    for i in range(2**list_length):
        modified_numbers = []

        # Build the current combination of added/subtracted numbers
        for j in range(list_length):
            if (i >> j) & 1:
                modified_numbers.append(numbers[j] + some_value)
            else:
                modified_numbers.append(numbers[j] - some_value)

        # Find max and min of the modified array
        maximum_value = max(modified_numbers)

        minimum_value = min(modified_numbers)

        # Update smallest range if needed
        smallest_range = min(smallest_range, maximum_value - minimum_value)

    return smallest_range

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, arrange the numbers in increasing order.
Consider that the sorted numbers will be either increased or decreased by a fixed amount. Focus on the point where the numbers transition from being decreased to being increased.
Imagine a 'pivot' point within the sorted set. All numbers before the pivot will be increased, and all numbers after the pivot will be decreased.
For each possible pivot point, calculate the potential new maximum and minimum values after applying the increase/decrease.
The potential new maximum will be either the largest original number decreased, or the number right before the pivot increased.
The potential new minimum will be either the smallest original number increased, or the number right after the pivot decreased.
Calculate the difference between the potential maximum and minimum for each pivot choice.
Find the smallest difference among all these pivot choices. This is the smallest possible range.

Code Implementation

def smallest_range_two(numbers, add_subtract_value):
    numbers.sort()
    array_length = len(numbers)
    initial_difference = numbers[-1] - numbers[0]
    smallest_range = initial_difference

    for i in range(array_length - 1):
        # Consider each element as a potential pivot
        potential_maximum = max(numbers[-1] - add_subtract_value, numbers[i] + add_subtract_value)

        # Determine the potential minimum value
        potential_minimum = min(numbers[0] + add_subtract_value, numbers[i+1] - add_subtract_value)

        smallest_range = min(smallest_range, potential_maximum - potential_minimum)

    return smallest_range

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is null or empty, as no range can be calculated.
Single element array	Return 0 since the range is zero if there is only one element.
Array with two identical elements and K=0	Return 0 since the range remains 0 after potentially adding/subtracting 0.
Array with two identical elements and large K	Handle the K value correctly to ensure the minimum difference between the altered identical elements are calculated correctly by either adding K to the smaller and subtracting K to the larger or vice versa.
Array with all identical values	The range will always be zero regardless of K's value; handle addition/subtraction of K correctly.
K is zero	Return the original range (max - min) as no change occurs.
Large input array with large values and large K	Ensure that integer overflow does not occur during calculations by using long data type.
Array is already sorted or reverse sorted	The algorithm should correctly adjust the values regardless of the initial order of the array.

Empty or null input array

How to Handle:

Return 0 if the input array is null or empty, as no range can be calculated.

Single element array

How to Handle:

Return 0 since the range is zero if there is only one element.

Array with two identical elements and K=0

How to Handle:

Return 0 since the range remains 0 after potentially adding/subtracting 0.

Array with two identical elements and large K

How to Handle:

Array with all identical values

How to Handle:

The range will always be zero regardless of K's value; handle addition/subtraction of K correctly.

K is zero

How to Handle:

Return the original range (max - min) as no change occurs.

Large input array with large values and large K

How to Handle:

Ensure that integer overflow does not occur during calculations by using long data type.

Array is already sorted or reverse sorted

How to Handle:

The algorithm should correctly adjust the values regardless of the initial order of the array.