Problem Description

You are given a 0-indexed integer array nums. Your task is to repeatedly perform an operation that removes pairs of equal integers from the array.

In each operation, you:

• Choose two integers in nums that are equal
• Remove both integers from nums, forming a pair

You continue performing this operation as many times as possible until no more pairs can be formed.

Return a 0-indexed integer array answer of size 2 where:

• answer[0] is the total number of pairs that are formed
• answer[1] is the number of leftover integers remaining in nums after all possible pairs have been removed

For example, if nums = [1, 3, 2, 1, 3, 2, 2], you can form:

• One pair of 1's (removing two 1's)
• One pair of 3's (removing two 3's)
• One pair of 2's (removing two 2's)

This gives you 3 pairs total, with 1 leftover integer (the remaining 2), so the answer would be [3, 1].

The solution counts the frequency of each number in the array. For each number that appears v times, you can form v // 2 pairs (integer division). The total number of pairs is the sum of v // 2 for all distinct numbers. The leftover count is simply the original array length minus twice the number of pairs formed.

Intuition

The key insight is that we need to count how many pairs we can form from equal elements. Think about it this way: if a number appears multiple times in the array, we can only form pairs from those occurrences.

For instance, if the number 5 appears 7 times, we can form 7 // 2 = 3 pairs, leaving 1 occurrence of 5 unpaired. This is because each pair consumes exactly 2 equal numbers.

This naturally leads us to a frequency counting approach:

1. First, count how many times each unique number appears in the array
2. For each unique number with frequency v, we can form exactly v // 2 pairs
3. The total pairs is the sum of all individual pair counts

The elegance of this approach is that we don't need to actually perform the removal operations. We can directly calculate the final result mathematically:

• Total pairs = sum of (frequency // 2) for all unique numbers
• Leftover elements = original array length - (total pairs × 2)

The multiplication by 2 in the leftover calculation makes sense because each pair removes exactly 2 elements from the original array.

This transforms what could be a complex simulation problem into a simple counting problem that can be solved in linear time with a single pass through the frequency counts.

Solution Approach

The implementation uses a counting strategy with a hash table to efficiently solve the problem.

Step 1: Count Frequencies

cnt = Counter(nums)

We use Python's Counter from the collections module to create a frequency map. This gives us a dictionary where keys are the unique numbers from nums and values are their occurrence counts.

Step 2: Calculate Total Pairs

s = sum(v // 2 for v in cnt.values())

We iterate through all frequency values in the counter. For each frequency v:

• v // 2 gives us the number of pairs we can form from that specific number
• We sum all these individual pair counts to get the total number of pairs s

For example, if cnt = {1: 5, 2: 3, 4: 6}:

• Number 1 appears 5 times → can form 5 // 2 = 2 pairs
• Number 2 appears 3 times → can form 3 // 2 = 1 pair
• Number 4 appears 6 times → can form 6 // 2 = 3 pairs
• Total pairs s = 2 + 1 + 3 = 6

Step 3: Calculate Leftover Elements

return [s, len(nums) - s * 2]

• s * 2 represents the total number of elements used to form pairs (each pair uses 2 elements)
• len(nums) - s * 2 gives us the count of leftover elements that couldn't form pairs

The time complexity is O(n) where n is the length of the input array, as we iterate through the array once to build the counter and then iterate through the unique values once more. The space complexity is O(k) where k is the number of unique elements in the array.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 2, 1, 3, 2, 2].

Step 1: Count Frequencies

First, we count how many times each number appears:

• Number 1 appears 2 times
• Number 2 appears 3 times
• Number 3 appears 2 times

So our frequency map is: {1: 2, 2: 3, 3: 2}

Step 2: Calculate Pairs for Each Number

For each unique number, we determine how many pairs we can form:

• Number 1 with frequency 2: 2 // 2 = 1 pair
• Number 2 with frequency 3: 3 // 2 = 1 pair (one 2 will be left over)
• Number 3 with frequency 2: 2 // 2 = 1 pair

Total pairs: 1 + 1 + 1 = 3

Step 3: Calculate Leftover Elements

We started with 7 elements in total (len(nums) = 7). We formed 3 pairs, which used 3 × 2 = 6 elements. Leftover elements: 7 - 6 = 1

Final Answer: [3, 1]

This matches our expectation - we formed 3 pairs (one pair each of 1's, 2's, and 3's), and we have 1 leftover element (the third occurrence of 2 that couldn't form a pair).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the Counter requires iterating through all n elements once: O(n)
• Iterating through the Counter values to calculate the sum takes O(C) time, where C is the number of unique elements
• Since C ≤ n, the overall time complexity is O(n)

The space complexity is O(C), where C is the number of unique elements in nums. In this problem, since the range of numbers is limited to 101 possible values (as mentioned in the reference), the space complexity is effectively O(101) = O(1) in the worst case. The Counter dictionary stores at most C key-value pairs, where C represents the distinct integers in the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Modify the Array While Iterating

A common mistake is trying to remove pairs directly from the original array while iterating through it:

# INCORRECT APPROACH
def numberOfPairs(self, nums: List[int]) -> List[int]:
    pairs = 0
    i = 0
    while i < len(nums):
        j = i + 1
        while j < len(nums):
            if nums[i] == nums[j]:
                nums.pop(j)  # Removing elements while iterating
                nums.pop(i)  # This causes index shifting issues
                pairs += 1
                break
            j += 1
        else:
            i += 1
    return [pairs, len(nums)]

Why it's problematic:

• Modifying a list while iterating causes index shifting, leading to skipped elements or index out of bounds errors
• Time complexity becomes O(n³) due to the nested loops and list removal operations
• The logic becomes complex and error-prone

Solution: Use the frequency counting approach instead of modifying the original array.

Pitfall 2: Incorrect Leftover Calculation

Some might incorrectly calculate leftovers using modulo operations on individual frequencies:

# INCORRECT APPROACH
def numberOfPairs(self, nums: List[int]) -> List[int]:
    cnt = Counter(nums)
    pairs = sum(v // 2 for v in cnt.values())
    leftovers = sum(v % 2 for v in cnt.values())  # Wrong calculation
    return [pairs, leftovers]

Why it's problematic:

• v % 2 only gives 0 or 1 for each unique number, not the actual count of leftover elements
• For example, if a number appears 5 times, 5 % 2 = 1, but we actually have 1 leftover element of that specific number

Solution: Calculate leftovers as len(nums) - pairs * 2, which correctly accounts for the total elements removed.

Pitfall 3: Using Nested Loops for Pair Finding

Implementing a brute force O(n²) solution with nested loops:

# INEFFICIENT APPROACH
def numberOfPairs(self, nums: List[int]) -> List[int]:
    used = [False] * len(nums)
    pairs = 0
  
    for i in range(len(nums)):
        if used[i]:
            continue
        for j in range(i + 1, len(nums)):
            if not used[j] and nums[i] == nums[j]:
                used[i] = used[j] = True
                pairs += 1
                break
  
    leftovers = sum(1 for u in used if not u)
    return [pairs, leftovers]

Why it's problematic:

• O(n²) time complexity is unnecessarily slow for large inputs
• More complex logic with boolean tracking arrays
• Higher chance of implementation errors

Solution: Use the O(n) frequency counting approach which is both faster and simpler to implement.