Jobs

Interviews

Discussions

Smallest Range I

Easy

Asked by:

16 views

Topics:

Arrays

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

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: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints:

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

Try coding it in LeetCode

Smallest Range I

Easy

Asked by:

16 views

Topics:

Arrays

You are given an integer array nums and an integer k.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

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: 0
Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

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 constraints on the size of the `nums` array and the range of values within the array and for `k`?
Can `nums` be empty or null? If so, what should I return?
Is `k` guaranteed to be non-negative?
If all the numbers in `nums` can be made equal after applying the operation, what should I return (specifically if max - min would be 0)?
Are the numbers in `nums` integers only, or could they be floating-point numbers?

Brute Force Solution

Approach

The brute force way to find the smallest range involves checking every possible adjustment we can make to each number. We'll try adding or subtracting the maximum allowed adjustment from each number, then calculate the range between the biggest and smallest numbers after these adjustments.

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

For each possible combination of adding or subtracting the adjustment value from each number, do the following:
Adjust each number in the input by either adding the adjustment value or subtracting the adjustment value.
Find the largest and smallest numbers among the adjusted numbers.
Calculate the difference between the largest and smallest adjusted numbers. This difference is the range.
Keep track of the smallest range you've found so far.
After checking all possible combinations of adjustments, return the smallest range you kept track of.

Code Implementation

def smallest_range_brute_force(numbers, allowable_amount):
    smallest_range = float('inf')

    # Iterate through each number in the input list
    for index in range(len(numbers)):

        # Try adding the allowable amount to the number
        adjusted_numbers_addition = numbers[:]
        adjusted_numbers_addition[index] += allowable_amount

        maximum_value_addition = max(adjusted_numbers_addition)
        minimum_value_addition = min(adjusted_numbers_addition)
        current_range_addition = maximum_value_addition - minimum_value_addition
        smallest_range = min(smallest_range, current_range_addition)

        # Try subtracting the allowable amount from the number
        adjusted_numbers_subtraction = numbers[:]
        adjusted_numbers_subtraction[index] -= allowable_amount

        maximum_value_subtraction = max(adjusted_numbers_subtraction)
        minimum_value_subtraction = min(adjusted_numbers_subtraction)
        current_range_subtraction = maximum_value_subtraction - minimum_value_subtraction
        smallest_range = min(smallest_range, current_range_subtraction)

    return smallest_range

Big(O) Analysis

Time Complexity

O(2^n) – The provided solution considers every possible combination of adding or subtracting k from each number in the input array. Since each of the n numbers can either have k added or subtracted, there are 2 options for each number. Therefore, the total number of combinations is 2 * 2 * ... * 2 (n times), which is 2^n. For each of these 2^n combinations, we iterate through the n numbers to adjust them, find the maximum and minimum, and calculate the range, taking O(n) time. Thus, the overall time complexity is O(n * 2^n). However, since 2^n grows much faster than n, the dominant term is 2^n.

Space Complexity

O(1) – The described brute force approach iterates through different combinations of adding or subtracting the adjustment value. It calculates the range (max - min) for each combination. The only auxiliary space used is for storing the current smallest range found so far (a single number) and possibly a few variables to hold the maximum and minimum values within each adjusted array. These variables occupy constant space, irrespective of the input array's 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 group after making adjustments to each number. Instead of changing every number, we can focus on the largest and smallest values to bring them closer together. By moving the largest number down and the smallest number up as much as possible, we can quickly find the smallest possible range.

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

Find the largest and smallest numbers in the group.
Determine how much each number can be changed, both up and down.
Calculate how much the largest number can decrease and the smallest number can increase.
Subtract the amount the largest number can decrease from its initial value.
Add the amount the smallest number can increase to its initial value.
Compare the adjusted largest and smallest numbers. If the adjusted smallest number is bigger than or equal to the adjusted largest number, the range is zero.
If the adjusted largest number is still bigger than the adjusted smallest number, calculate the difference between them. This is the smallest possible range.

Code Implementation

def smallest_range(number_list, adjustment_value):
    largest_number = max(number_list)
    smallest_number = min(number_list)

    # If the range can be reduced to zero.
    if smallest_number + adjustment_value >= largest_number - adjustment_value:
        return 0

    # Calculate smallest possible range.
    smallest_possible_range = (largest_number - adjustment_value) - \
                                 (smallest_number + adjustment_value)

    # Return the result.
    return smallest_possible_range

Big(O) Analysis

Time Complexity

O(n) – The algorithm first finds the largest and smallest numbers in the input array. This requires iterating through all n elements of the array once. The subsequent calculations involve only constant time arithmetic operations. Therefore, the dominant operation is finding the minimum and maximum, which takes O(n) time.

Space Complexity

O(1) – The algorithm only uses a few constant space variables to store the maximum and minimum values and to hold the intermediate results of calculations. The amount of extra memory used does not depend on the number of elements (N) in the input array. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since there are no numbers to modify and thus the difference between max and min is zero.
Array with only one element	Return 0 since there's only one number and the difference between the (same) max and min is zero.
k is zero	The score is the original difference between max and min of the input array.
All elements in the array are identical	The minimum score is 0, achievable by adding 0 to each element.
k is very large (larger than half the difference between max and min)	The minimum score will be 0, because all numbers can be made equal by adding or subtracting k.
Array with large positive and negative numbers	The min and max values could potentially lead to integer overflow when computing the difference, so use long to handle it.
Input array is already at its minimum possible score of 0	The algorithm should still correctly return 0 since the difference between max and min is 0 already.
Negative k value	The problem statement defined k as an integer and [-k, k] should be the proper range for the addition, and we should take the absolute value to keep its logic.

Empty or null input array

How to Handle:

Return 0 since there are no numbers to modify and thus the difference between max and min is zero.

Array with only one element

How to Handle:

Return 0 since there's only one number and the difference between the (same) max and min is zero.

k is zero

How to Handle:

The score is the original difference between max and min of the input array.

All elements in the array are identical

How to Handle:

The minimum score is 0, achievable by adding 0 to each element.

k is very large (larger than half the difference between max and min)

How to Handle:

The minimum score will be 0, because all numbers can be made equal by adding or subtracting k.

Array with large positive and negative numbers

How to Handle:

The min and max values could potentially lead to integer overflow when computing the difference, so use long to handle it.

Input array is already at its minimum possible score of 0

How to Handle:

The algorithm should still correctly return 0 since the difference between max and min is 0 already.

Negative k value

How to Handle:

The problem statement defined k as an integer and [-k, k] should be the proper range for the addition, and we should take the absolute value to keep its logic.

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 constraints on the size of the `nums` array and the range of values within the array and for `k`?
Can `nums` be empty or null? If so, what should I return?
Is `k` guaranteed to be non-negative?
If all the numbers in `nums` can be made equal after applying the operation, what should I return (specifically if max - min would be 0)?
Are the numbers in `nums` integers only, or could they be floating-point numbers?

Brute Force Solution

Approach

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

For each possible combination of adding or subtracting the adjustment value from each number, do the following:
Adjust each number in the input by either adding the adjustment value or subtracting the adjustment value.
Find the largest and smallest numbers among the adjusted numbers.
Calculate the difference between the largest and smallest adjusted numbers. This difference is the range.
Keep track of the smallest range you've found so far.
After checking all possible combinations of adjustments, return the smallest range you kept track of.

Code Implementation

def smallest_range_brute_force(numbers, allowable_amount):
    smallest_range = float('inf')

    # Iterate through each number in the input list
    for index in range(len(numbers)):

        # Try adding the allowable amount to the number
        adjusted_numbers_addition = numbers[:]
        adjusted_numbers_addition[index] += allowable_amount

        maximum_value_addition = max(adjusted_numbers_addition)
        minimum_value_addition = min(adjusted_numbers_addition)
        current_range_addition = maximum_value_addition - minimum_value_addition
        smallest_range = min(smallest_range, current_range_addition)

        # Try subtracting the allowable amount from the number
        adjusted_numbers_subtraction = numbers[:]
        adjusted_numbers_subtraction[index] -= allowable_amount

        maximum_value_subtraction = max(adjusted_numbers_subtraction)
        minimum_value_subtraction = min(adjusted_numbers_subtraction)
        current_range_subtraction = maximum_value_subtraction - minimum_value_subtraction
        smallest_range = min(smallest_range, current_range_subtraction)

    return smallest_range

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Find the largest and smallest numbers in the group.
Determine how much each number can be changed, both up and down.
Calculate how much the largest number can decrease and the smallest number can increase.
Subtract the amount the largest number can decrease from its initial value.
Add the amount the smallest number can increase to its initial value.
Compare the adjusted largest and smallest numbers. If the adjusted smallest number is bigger than or equal to the adjusted largest number, the range is zero.
If the adjusted largest number is still bigger than the adjusted smallest number, calculate the difference between them. This is the smallest possible range.

Code Implementation

def smallest_range(number_list, adjustment_value):
    largest_number = max(number_list)
    smallest_number = min(number_list)

    # If the range can be reduced to zero.
    if smallest_number + adjustment_value >= largest_number - adjustment_value:
        return 0

    # Calculate smallest possible range.
    smallest_possible_range = (largest_number - adjustment_value) - \
                                 (smallest_number + adjustment_value)

    # Return the result.
    return smallest_possible_range

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since there are no numbers to modify and thus the difference between max and min is zero.
Array with only one element	Return 0 since there's only one number and the difference between the (same) max and min is zero.
k is zero	The score is the original difference between max and min of the input array.
All elements in the array are identical	The minimum score is 0, achievable by adding 0 to each element.
k is very large (larger than half the difference between max and min)	The minimum score will be 0, because all numbers can be made equal by adding or subtracting k.
Array with large positive and negative numbers	The min and max values could potentially lead to integer overflow when computing the difference, so use long to handle it.
Input array is already at its minimum possible score of 0	The algorithm should still correctly return 0 since the difference between max and min is 0 already.
Negative k value	The problem statement defined k as an integer and [-k, k] should be the proper range for the addition, and we should take the absolute value to keep its logic.

Empty or null input array

How to Handle:

Return 0 since there are no numbers to modify and thus the difference between max and min is zero.

Array with only one element

How to Handle:

Return 0 since there's only one number and the difference between the (same) max and min is zero.

k is zero

How to Handle:

The score is the original difference between max and min of the input array.

All elements in the array are identical

How to Handle:

The minimum score is 0, achievable by adding 0 to each element.

k is very large (larger than half the difference between max and min)

How to Handle:

The minimum score will be 0, because all numbers can be made equal by adding or subtracting k.

Array with large positive and negative numbers

How to Handle:

The min and max values could potentially lead to integer overflow when computing the difference, so use long to handle it.

Input array is already at its minimum possible score of 0

How to Handle:

The algorithm should still correctly return 0 since the difference between max and min is 0 already.

Negative k value

How to Handle:

The problem statement defined k as an integer and [-k, k] should be the proper range for the addition, and we should take the absolute value to keep its logic.