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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Removing Minimum and Maximum From Array

Number: 2212

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a 0-indexed array of distinct integers, remove both the minimum and maximum elements by only deleting elements from the front or the back of the array. The goal is to determine the minimum number of deletions needed to remove both these elements.

Key Insights

  • First, determine the indices of the minimum and maximum elements.
  • Since deletions can only occur from either end of the array, consider three strategies:
    • Removing both elements by deleting from the front.
    • Removing both elements by deleting from the back.
    • Removing one element from the front and the other from the back.
  • Choose the strategy that minimizes the total number of deletions.

Space and Time Complexity

Time Complexity: O(n) – We iterate through the array once to locate the minimum and maximum elements. Space Complexity: O(1) – Only a constant amount of extra space is used.

Solution

The solution involves:

  1. Iterating through the array to find the positions (indices) of the minimum and maximum elements.
  2. Considering three potential deletion strategies:
    • Remove from the front until the farther of the two indices is removed.
    • Remove from the back until the closer of the two indices (from the back) is removed.
    • Remove one element from the front (up to the smaller index) and the other from the back (from the larger index).
  3. Computing the number of deletions for each strategy and returning the minimum value.

Data structures used include simple integer variables to store indices and counts. The approach is greedy because at each step, we choose the deletion direction that minimizes the overall count.

Code Solutions

# Python solution with line-by-line comments
def minimum_deletions(nums):
    n = len(nums)  # Length of the array
    
    # Find the index of the minimum and maximum elements
    min_index = nums.index(min(nums))
    max_index = nums.index(max(nums))
    
    # Ensure min_index is the smaller index for consistency
    if min_index > max_index:
        min_index, max_index = max_index, min_index
    
    # Option 1: Remove both from the front
    remove_front = max_index + 1
    
    # Option 2: Remove both from the back
    remove_back = n - min_index
    
    # Option 3: Remove one from the front and one from the back
    remove_mixed = (min_index + 1) + (n - max_index)
    
    # Return the minimum number of deletions among the strategies
    return min(remove_front, remove_back, remove_mixed)

# Example usage:
nums1 = [2,10,7,5,4,1,8,6]
print(minimum_deletions(nums1))  # Expected output: 5
← Back to All Questions