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

Minimum Array Length After Pair Removals

Number: 3081

Difficulty: Medium

Paid? No

Companies: Snowflake

Problem Description

Given a non-decreasing sorted integer array nums, you can repeatedly remove two elements nums[i] and nums[j] (i and j being indices in the current array) provided that nums[i] < nums[j]. After each removal, the remaining elements keep their original order. Determine the minimum length of nums possible after applying zero or more such removal operations.

Key Insights

  • The array is sorted so identical elements are grouped together.
  • A valid removal requires two elements where the smaller one comes before a larger one.
  • The maximum number of removals is determined by how many pairs can be formed where the first element is strictly less than the second.
  • A two-pointer greedy strategy can count the maximum pairs: one pointer for potential smaller elements and another pointer for potential larger ones.
  • The minimal remaining length is the original length minus twice the number of valid pairs.

Space and Time Complexity

Time Complexity: O(n) - Single pass using two pointers. Space Complexity: O(1) - Constant extra space.

Solution

The idea is to use two pointers. Start the first pointer (i) at the beginning of the array (to iterate over smaller candidates) and the second pointer (j) starting roughly at the middle of the array (as candidates for larger numbers). For each potential pair, if nums[i] is strictly less than nums[j], we form a pair and move both pointers forward. Otherwise, only move j until a valid pairing is found. The maximum number of valid pairs is then used to calculate the minimum remaining length as length(nums) - 2 * (number of pairs).

Code Solutions

# Python solution with line-by-line comments

def min_length_after_removals(nums):
    # Get the number of elements in nums
    n = len(nums)
    # Initialize two pointers: 
    # pointer i for the smaller values candidate and pointer j for the larger candidate
    i, j = 0, n // 2  # start j from the middle
    pairs = 0  # counts the number of valid pairs formed
    # Iterate while both pointers are within bounds
    while i < n // 2 and j < n:
        # If the candidate at i is strictly less than candidate at j, a valid pair is found
        if nums[i] < nums[j]:
            pairs += 1     # Increment pairs count
            i += 1         # Move to next candidate for the smaller element
            j += 1         # Move to next candidate for the larger element
        else:
            # Otherwise, move pointer j to find a strictly larger number
            j += 1
    # The remaining length is the original array length minus twice the number of pairs removed
    return n - 2 * pairs

# Example usage:
nums1 = [1,2,3,4]         # Expected output: 0
nums2 = [1,1,2,2,3,3]     # Expected output: 0
nums3 = [1000000000,1000000000] # Expected output: 2
nums4 = [2,3,4,4,4]       # Expected output: 1

print(min_length_after_removals(nums1))
print(min_length_after_removals(nums2))
print(min_length_after_removals(nums3))
print(min_length_after_removals(nums4))
← Back to All Questions