We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Removing Minimum and Maximum From Array

Difficulty: Medium

Problem Description

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

Key Insights

  • The minimum and maximum values in the array can be found using a single pass through the array.
  • There are four strategies for removing the minimum and maximum:
    1. Remove both from the front.
    2. Remove both from the back.
    3. Remove minimum from the front and maximum from the back.
    4. Remove maximum from the front and minimum from the back.
  • The minimum deletions required will be the least among these strategies.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will first identify the indices of the minimum and maximum elements in the array. Then, we will calculate the number of deletions required for each of the four strategies mentioned. The minimum number of deletions across these strategies will be our answer. The use of simple integer comparisons and arithmetic allows us to maintain a space complexity of O(1).

Code Solutions

def minimumDeletions(nums):
    min_index = nums.index(min(nums))
    max_index = nums.index(max(nums))
    
    # Calculate the four possible scenarios
    front_remove = max(min_index, max_index) + 1  # Remove both from front
    back_remove = len(nums) - min(min_index, max_index)  # Remove both from back
    front_back_remove = min_index + 1 + (len(nums) - max_index)  # Remove min from front and max from back
    back_front_remove = max_index + 1 + (len(nums) - min_index)  # Remove max from front and min from back
    
    # Return the minimum of the four strategies
    return min(front_remove, back_remove, front_back_remove, back_front_remove)
← Back to All Questions