Removing Minimum and Maximum From Array

Medium

Asked by:

21 views

Topics:

Arrays

You are given a 0-indexed array of distinct integers nums.

There is an element in nums that has the lowest value and an element that has the highest value. We call them the minimum and maximum respectively. Your goal is to remove both these elements from the array.

A deletion is defined as either removing an element from the front of the array or removing an element from the back of the array.

Return the minimum number of deletions it would take to remove both the minimum and maximum element from the array.

Example 1:

Input: nums = [2,10,7,5,4,1,8,6]
Output: 5
Explanation: 
The minimum element in the array is nums[5], which is 1.
The maximum element in the array is nums[1], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

Example 2:

Input: nums = [0,-4,19,1,8,-2,-3,5]
Output: 3
Explanation: 
The minimum element in the array is nums[1], which is -4.
The maximum element in the array is nums[2], which is 19.
We can remove both the minimum and maximum by removing 3 elements from the front.
This results in only 3 deletions, which is the minimum number possible.

Example 3:

Input: nums = [101]
Output: 1
Explanation:  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

Constraints:

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
The integers in nums are distinct.

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 is the data type of the array elements? Are they integers, floats, or something else?
What should I return if the input array is empty or null?
Are there any constraints on the values within the array? (e.g., a maximum or minimum value)
If there are multiple minimum or maximum values, should I remove all occurrences of the minimum and maximum, or just one of each?
Should I return a new array with the elements removed, or modify the original array in-place?

Brute Force Solution

Approach

The most straightforward way to solve this is to look at every possible way to remove one smallest and one largest number from the set. We'll then pick the best removal strategy. It's like trying every single combination until you find the winning one.

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

First, imagine you remove the actual smallest number and the actual largest number from the group.
Then, imagine you remove the smallest number and the second largest number from the group.
Keep doing this, trying every possible pairing of one smallest number and one largest number that you could remove.
For each of these imagined removals, count how many numbers you had to skip over on each side to remove your chosen minimum and maximum values.
Finally, choose the combination of removals that requires you to skip over the fewest numbers.

Code Implementation

def removing_minimum_and_maximum_from_array(numbers):
    array_length = len(numbers)
    minimum_skips = array_length  # Initialize with worst case

    for minimum_index in range(array_length):
        for maximum_index in range(array_length):

            # Ensure we're considering distinct elements
            if minimum_index == maximum_index:
                continue

            # Determine indices of min and max values.
            minimum_value = numbers[minimum_index]
            maximum_value = numbers[maximum_index]

            is_valid_pair = True
            for index in range(array_length):
                if index != minimum_index and numbers[index] < minimum_value:
                    is_valid_pair = False
                    break
                if index != maximum_index and numbers[index] > maximum_value:
                    is_valid_pair = False
                    break

            if not is_valid_pair:
                continue

            # Calculate skips from left and right
            left_skips = max(minimum_index, maximum_index) + 1

            # To the right, the elements we remove are also skipped
            right_skips = array_length - min(minimum_index, maximum_index)

            current_skips = min(left_skips, right_skips)

            # Keep track of the best case skips
            if current_skips < minimum_skips:
                minimum_skips = current_skips

    return minimum_skips

Big(O) Analysis

Time Complexity

O(n²) – The algorithm, as described, iterates through all possible pairs of minimum and maximum values in the array. Finding the minimum and maximum elements initially takes O(n) time. However, the core of the algorithm involves considering all possible pairs of one smallest and one largest number, which amounts to a nested loop-like operation. Specifically, for each potentially smallest number, the algorithm considers all potentially largest numbers. Therefore, the number of such pairs is proportional to n * n, leading to approximately n * n / 2 operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The described algorithm iterates through potential minimum/maximum pairs without storing intermediate collections of these pairs or skipped elements. It calculates the number of skipped elements on the fly for each pair. The algorithm only needs to store a few integer variables like indices and counters which take constant space regardless of the input array size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The trick is to realize you only need to check removing elements from the start, from the end, or from both. We efficiently figure out the costs of these scenarios and pick the cheapest one.

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

Find the positions of the smallest and largest values in the collection.
Calculate the cost of removing everything up to and including the furthest of those two positions from the start.
Calculate the cost of removing everything from the closest of those two positions to the end of the collection.
Calculate the cost of removing everything from the start up to the smallest position and everything from the largest position to the end.
Pick the smallest of these three costs. That will be the minimum number of removals you need to do.

Code Implementation

def removing_minimum_and_maximum(numbers):
    array_length = len(numbers)
    minimum_value_index = numbers.index(min(numbers))
    maximum_value_index = numbers.index(max(numbers))

    # Find the furthest index to remove from the start.
    farthest_index = max(minimum_value_index, maximum_value_index)

    # Find the closest index to remove from the end.
    closest_index = min(minimum_value_index, maximum_value_index)

    removal_from_start_cost = farthest_index + 1

    removal_from_end_cost = array_length - closest_index

    # Calculate the cost of removing from both ends.
    removal_from_both_ends_cost = (minimum_value_index + 1) + (array_length - maximum_value_index)

    # Calculate cost if max index is smaller than min index
    if maximum_value_index < minimum_value_index:
         removal_from_both_ends_cost = (maximum_value_index + 1) + (array_length - minimum_value_index)

    # Determine the minimum number of removals required
    minimum_removals = min(removal_from_start_cost, removal_from_end_cost, removal_from_both_ends_cost)

    return minimum_removals

Big(O) Analysis

Time Complexity

O(n) – Finding the minimum and maximum values requires iterating through the array once, which is O(n). The remaining steps involve a fixed number of arithmetic operations and comparisons based on the indices of the minimum and maximum elements; these are constant time operations O(1). Therefore, the overall time complexity is dominated by the initial search for minimum and maximum, resulting in O(n).

Space Complexity

O(1) – The algorithm finds the indices of the minimum and maximum elements and stores them in variables. These variables, regardless of the input array's size N, occupy constant space. No auxiliary data structures like arrays or hash maps are used. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or undefined input array	Return an empty list or throw an IllegalArgumentException to prevent NullPointerException.
Empty array	Return 0 since no removal is needed.
Array with one element	Return 0 since the single element is both min and max and needs to be removed, thus zero operations.
Array with two elements	Return 1 since removing both min and max is optimal which requires one operation.
Array with all elements being the same	Return Math.min(first element index + 1, array length - first element index) as either from the beginning or the end will be the same.
Array with a large number of elements, potentially causing integer overflow when calculating indices or distances.	Use long data type for index calculations if the array size is large to avoid integer overflow.
Array with negative numbers, zeros, and positive numbers mixed	The standard min/max finding algorithms work correctly regardless of the number signs.
The minimum and maximum values are at the beginning and the end of the array respectively (or vice-versa).	Return 1, as we only need to remove elements from one end.

Null or undefined input array

How to Handle:

Return an empty list or throw an IllegalArgumentException to prevent NullPointerException.

Empty array

How to Handle:

Return 0 since no removal is needed.

Array with one element

How to Handle:

Return 0 since the single element is both min and max and needs to be removed, thus zero operations.

Array with two elements

How to Handle:

Return 1 since removing both min and max is optimal which requires one operation.

Array with all elements being the same

How to Handle:

Return Math.min(first element index + 1, array length - first element index) as either from the beginning or the end will be the same.

Array with a large number of elements, potentially causing integer overflow when calculating indices or distances.

How to Handle:

Use long data type for index calculations if the array size is large to avoid integer overflow.

Array with negative numbers, zeros, and positive numbers mixed

How to Handle:

The standard min/max finding algorithms work correctly regardless of the number signs.

The minimum and maximum values are at the beginning and the end of the array respectively (or vice-versa).

How to Handle:

Return 1, as we only need to remove elements from one end.