Problem Informations

• Problem Index: 2206
• Problem Link: Divide Array Into Equal Pairs
• Topics: Array, Hash Table, Bit Manipulation, Counting

Problem Description

You are given an integer array nums consisting of $2 \times n$ integers.

You need to divide nums into $n$ pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return true if nums can be divided into $n$ pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

• nums.length == 2 * n
• $1 \leq n \leq 500$
• $1 \leq nums[i] \leq 500$

Intuition

The problem presents the challenge of partitioning an array into pairs where each pair contains identical elements. Given that the array’s size is always even, a direct implication is that for such a partitioning to be possible, each element must appear an even number of times. The key insight here is that pairing is feasible if and only if every number occurs in pairs.

Approach

To solve the problem, we leverage a bitset to efficiently track the parity (even or odd count) of each number’s occurrence in the nums array.

1. Initialization: Construct a bitset that can handle indices corresponding to potential values of nums. Given the constraints, we use a bitset of size 501 since nums[i] ranges from 1 to 500.

2. Tracking Occurrences: Iterate over each integer num in the nums array. For each occurrence of num, flip its corresponding bit in the bitset. This flip operation changes a zero bit to one (indicating an odd appearance) or a one bit to zero (indicating an even appearance).

3. Verification: After processing all numbers, check the bitset. If all elements can be paired, every number must have appeared an even number of times, resulting in all bits being zero in the bitset.

4. Return Result: Finally, return true if the count of set bits in the bitset is zero, indicating every number can be perfectly paired; otherwise, return false. This condition ensures each number’s presence in the nums array is even.

Code

C++

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        // Create a bitset to track the existence of numbers.
        bitset<501> existence;

        // Traverse each number in the nums array.
        for (int num : nums) {
            // Flip the bit corresponding to the current number.
            existence.flip(num);
        }

        // If the count of set bits is 0, it means all numbers can be paired.
        return (existence.count() == 0);
    }
};

Python

class Solution:
    def divideArray(self, nums):
        # Create a set to track the existence of numbers.
        existence = set()

        # Traverse each number in the nums array.
        for num in nums:
            # If the number is already in the set, remove it; otherwise, add it.
            if num in existence:
                existence.remove(num)
            else:
                existence.add(num)

        # If the set is empty, it means all numbers can be paired.
        return len(existence) == 0

Complexity

• Time complexity: $O(m)$
  The implementation iterates through the nums array while flipping bits in a bitset of constant size. Since the operations for each element (flip and count) are performed in constant time, the time complexity is $O(m)$, where $m$ is the number of elements in nums.
• Space complexity: $O(1)$
  The space required is determined by the size of the bitset, which is fixed at 501 bits. Regardless of the input size, this space usage remains constant, thus the space complexity is $O(1)$.