Divide Array Into Equal Pairs

easy hash map counting

Problem

You are given an integer array nums that contains exactly 2 * n elements. Decide whether the array can be split into n pairs so that in every pair the two elements are equal. Each element must belong to exactly one pair.

Return true if such a complete pairing exists, otherwise false.

Inputnums = [3, 2, 3, 2, 2, 2]

Outputtrue

Value 3 appears twice → one pair (3, 3). Value 2 appears four times → two pairs (2, 2) and (2, 2). Every value has an even count, so the array splits into 3 equal pairs.

nums (comma-separated, even count)

def divide_array(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    for c in count.values():
        if c % 2 != 0:
            return False
    return True

function divideArray(nums) {
  const count = new Map();
  for (const x of nums) {
    count.set(x, (count.get(x) || 0) + 1);
  }
  for (const c of count.values()) {
    if (c % 2 !== 0) return false;
  }
  return true;
}

class Solution {
    public boolean divideArray(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        for (int c : count.values()) {
            if (c % 2 != 0) return false;
        }
        return true;
    }
}

bool divideArray(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) {
        count[x]++;
    }
    for (auto& p : count) {
        if (p.second % 2 != 0) return false;
    }
    return true;
}

Explanation

The pairs we are allowed to form are special: the two elements of a pair must be equal. That means a pair only ever uses up two copies of the same value — a 2 can only be paired with another 2, never with a 3.

So the actual order of the array does not matter at all. What matters is, for each distinct value, how many copies of it exist. If a value appears an even number of times, those copies pair up perfectly among themselves. If a value appears an odd number of times, at least one copy is always left without an equal partner, and the whole split fails.

That gives a one-pass plan. Walk through the array and tally each value in a hash map (value → count). Then scan the counts: the answer is true exactly when every count is even.

Walking through the default example nums = [3, 2, 3, 2, 2, 2]: after counting we have {3: 2, 2: 4}. The count for 3 is 2 (even) and the count for 2 is 4 (even), so both values pair up and the answer is true.

By contrast, something like [1, 1, 1, 2] gives counts {1: 3, 2: 1}; the odd counts mean a leftover 1 and a leftover 2 can never be paired, so the answer would be false.

We touch each of the 2n elements once to build the table and then look at each distinct count once, so the work is linear in the array size.

Time: O(n) Space: O(n)