Divide Array Into Equal Pairs

Difficulty: Easy | Acceptance: 79.20% | Paid: No Topics: Array, Hash Table, Bit Manipulation, Counting

You are given an integer array nums of even length n. You want to split the array into n / 2 pairs such that:

Each element belongs to exactly one pair. The elements present in a pair are equal. Return true if the array can be split into n / 2 pairs, otherwise return false.

• Examples
• Constraints
• Sorting
• Hash Map Frequency
• Bit Manipulation (Bitmask)

Examples

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.
The pairs are (3,3), (2,2), and (2,2).

Example 2:

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

Constraints

n == nums.length
2 <= n <= 500
n is even.
1 <= nums[i] <= 500

Sorting

Intuition If we sort the array, equal numbers will be adjacent to each other. We can then iterate through the array in steps of 2 and check if each number matches its neighbor.

Steps

• Sort the array in non-decreasing order.
• Iterate through the array with a step of 2 (i.e., check indices 0 and 1, then 2 and 3, etc.).
• If nums[i] is not equal to nums[i+1], return false.
• If the loop completes without mismatches, return true.

class Solution:
    def divideArray(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(0, len(nums), 2):
            if nums[i] != nums[i + 1]:
                return False
        return True

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm’s memory usage.
• Notes: Sorting modifies the input array or requires a copy. It is generally slower than linear time approaches but is very intuitive.

Hash Map Frequency

Intuition For a number to be divided into equal pairs, its total frequency in the array must be an even number. We can count the occurrences of each number and verify this condition.

Steps

• Initialize a hash map (or dictionary) to store the frequency of each number.
• Iterate through the array and update the counts in the hash map.
• Iterate through the values of the hash map.
• If any value is odd, return false.
• If all values are even, return true.

from collections import Counter

class Solution:
    def divideArray(self, nums: list[int]) -> bool:
        counts = Counter(nums)
        for count in counts.values():
            if count % 2 != 0:
                return False
        return True

Complexity

• Time: O(n) for iterating through the array and the map.
• Space: O(n) in the worst case to store the frequency of all distinct elements.
• Notes: This is the most general approach and works for any range of numbers.

Bit Manipulation (Bitmask)

Intuition Since the constraints specify that 1 <= nums[i] <= 500, we can use a bitmask to track the parity (odd or even count) of each number. We toggle the bit corresponding to the number. If a number appears an even number of times, its bit will be 0 at the end.

Steps

• Initialize a bitmask (or bitset) to 0.
• Iterate through each number in nums.
• Toggle the bit at the index corresponding to the number.
• After processing all numbers, check if the bitmask is 0 (all bits cleared).
• Return true if the mask is 0, otherwise false.

class Solution:
    def divideArray(self, nums: list[int]) -> bool:
        mask = 0
        for num in nums:
            mask ^= 1 << num
        return mask == 0

Complexity

• Time: O(n) to iterate through the array.
• Space: O(1) as the size of the bitmask is fixed (501 bits) regardless of input size n.
• Notes: This approach is extremely space-efficient and fast for small integer ranges.