Divide Array Into Equal Pairs

How it works

Instead of counting all frequencies, we can use a set to track elements with odd occurrences. When we see an element, if it is already in the set (meaning we have seen it an odd number of times), we remove it. If it is not in the set, we add it. At the end, if the set is empty, all elements appeared an even number of times.

Steps

1. Create an empty hash set.
2. Iterate through each element in the array.
3. If the element is in the set, remove it (completing a pair).
4. Otherwise, add it to the set (unpaired element).
5. After processing all elements, return true if the set is empty, false otherwise.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Checking for Pairs Instead of Even Counts

A common mistake is trying to actually form pairs and check if adjacent elements match after sorting. The problem only requires checking if each element appears an even number of times, not that the pairs are adjacent.

Forgetting the Array Length is Always Even

The problem guarantees that nums has 2n elements. Some solutions add unnecessary checks for odd-length arrays or forget that the total count of elements is always even, which simplifies the problem to just checking individual element frequencies.

from typing import List

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        odd_set = set()

        for num in nums:
            if num not in odd_set:
                odd_set.add(num)
            else:
                odd_set.remove(num)

        return not len(odd_set)

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        unordered_set<int> oddSet;

        for (int num : nums) {
            if (oddSet.count(num)) {
                oddSet.erase(num);
            } else {
                oddSet.insert(num);
            }
        }

        return oddSet.empty();
    }
};