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

Maximum Number of Pairs in Array

Number: 2421

Difficulty: Easy

Paid? No

Companies: Altimetrik

Problem Description

Given an integer array nums, you can repeatedly remove two equal integers from the array to form a pair. The goal is to determine the maximum number of such pairs that can be formed and the number of leftover elements after performing these pair-removals as many times as possible. The output should be a 0-indexed array where the first element is the total number of pairs formed and the second element is the count of leftover integers.

Key Insights

  • Count the frequency of each number in the array.
  • For each unique number, the number of pairs that can be formed is the frequency divided by two.
  • The total number of leftover integers is the sum of the remainders (frequency mod 2) over all unique numbers.
  • The problem can be solved in one pass (or two passes) over the array, making it efficient.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums. Space Complexity: O(n) in the worst-case scenario when all elements are unique.

Solution

The solution involves using a hash table (or dictionary) to count the frequency of each integer in the array. By iterating through the frequency counts, you can compute the number of pairs as the integer division of the frequency by 2. Simultaneously, the leftover count per number is obtained using the modulo operator (frequency % 2). Summing these values gives the final answer.

Code Solutions

# Python Code

def numberOfPairs(nums):
    # Dictionary to store frequency of each number
    frequency = {}
    
    # Count the frequency of each element in nums
    for num in nums:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    # Initialize counters for pairs and leftovers
    pairs = 0
    leftovers = 0
    
    # Iterate through frequency dictionary to calculate pairs and leftovers
    for count in frequency.values():
        pairs += count // 2  # number of pairs for the current number
        leftovers += count % 2  # leftover elements for the current number
        
    return [pairs, leftovers]

# Example Usage:
print(numberOfPairs([1,3,2,1,3,2,2]))  # Output: [3, 1]
← Back to All Questions