LeetCode 2206 - Divide Array Into Equal Pairs

LeetCode Problem 2206

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Bit Manipulation, Counting

Solution

Problem Understanding

The problem gives us an integer array nums containing exactly 2 * n elements. Our task is to determine whether it is possible to split the array into n valid pairs, where each pair contains two identical numbers.

In simpler terms, every number in the array must be matched with another occurrence of the same number. Since each element can only belong to one pair, every distinct number must appear an even number of times. If even one value appears an odd number of times, there will always be one leftover element that cannot be paired, making the answer false.

For example, if nums = [3,2,3,2,2,2], the number 3 appears twice and 2 appears four times. Since both frequencies are even, we can form pairs like (3,3), (2,2), and (2,2), so the answer is true.

On the other hand, if nums = [1,2,3,4], each number appears only once. Since none of them have a matching duplicate, it is impossible to form equal-value pairs, so the answer is false.

The constraints are important because they shape what kinds of solutions are practical:

• nums.length == 2 * n, meaning the array length is always even.
• 1 <= n <= 500, so the maximum array size is 1000.
• 1 <= nums[i] <= 500, meaning values are relatively small.

Since the array size is modest and numbers are bounded, counting frequencies is a very natural and efficient solution. The problem guarantees that the input length is always even, so we never need to handle malformed input with an odd number of elements.

Some important edge cases are worth recognizing early. If a number appears an odd number of times, pairing immediately becomes impossible. Arrays where all values are identical should return true, because every element can pair naturally. Arrays with many unique numbers can quickly fail if duplicates are missing. Single pair inputs, such as [5,5], should also work correctly.

Approaches

Brute Force Approach

A straightforward brute force strategy is to repeatedly search for a matching partner for each element. We could iterate through the array, pick an unused number, and scan the remaining elements to find an identical unused value. Once found, both elements are marked as paired.

This approach works because it explicitly attempts to build the required equal pairs. If every element finds a partner, the array can be divided successfully. If at any point a number has no matching unused value, the answer is false.

However, this method is inefficient because for every element we may scan much of the remaining array to locate a pair. In the worst case, this results in quadratic time complexity, which becomes unnecessarily slow compared to counting-based methods.

Optimal Approach, Frequency Counting

The key observation is that pairing is only possible if every distinct number appears an even number of times.

Instead of physically forming pairs, we can simply count how many times each number occurs. Once we know the frequencies, we check whether every count is divisible by 2. If all counts are even, valid pairing is guaranteed. If any count is odd, pairing becomes impossible.

This works because pairing equal numbers only depends on quantity. A value appearing 2, 4, or 6 times can always be partitioned into identical pairs. A value appearing 1, 3, or 5 times always leaves one unmatched element.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches for matching unused elements
Optimal	O(n)	O(n)	Counts frequencies and verifies all are even

Algorithm Walkthrough

1. Create a hash map to count occurrences of each number.

A hash map is ideal because it allows constant time insertion and lookup on average. The keys represent numbers in the array, and the values represent how many times each number appears. 2. Traverse the array once and update frequency counts.

For each number in nums, increment its count in the hash map. After this pass, we know exactly how many times every distinct value appears. 3. Iterate through all frequency values.

Examine every count stored in the hash map. 4. Check whether each frequency is even.

If any frequency is odd, immediately return False because one element would remain unmatched. 5. Return True if all counts are even.

If every number occurs an even number of times, then equal-value pairs can always be formed.

Why it works

The correctness relies on a simple invariant: a number can only be divided into equal pairs if it appears an even number of times. Since elements can only pair with identical values, every valid solution requires even frequencies. Conversely, if every frequency is even, we can always partition occurrences into pairs of identical numbers. Therefore, checking parity of frequencies is both necessary and sufficient.

Python Solution

from typing import List

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        frequency = {}

        for num in nums:
            frequency[num] = frequency.get(num, 0) + 1

        for count in frequency.values():
            if count % 2 != 0:
                return False

        return True

The implementation begins by creating a dictionary called frequency to store occurrence counts. During the first loop, every number in nums updates its corresponding count using get(num, 0) to safely handle unseen values.

Once counting is complete, the second loop iterates through all stored frequencies. The condition count % 2 != 0 checks whether a count is odd. If an odd count exists, the function immediately returns False because equal pairing becomes impossible.

If the loop finishes without finding any odd frequency, every value can be paired successfully, so the function returns True.

Go Solution

func divideArray(nums []int) bool {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	for _, count := range frequency {
		if count%2 != 0 {
			return false
		}
	}

	return true
}

The Go implementation closely mirrors the Python version. A map[int]int is used to store frequencies. Go maps automatically initialize missing integer values to 0, which makes incrementing straightforward with frequency[num]++.

Unlike Python, there is no need for a get() method because absent keys default to zero. Integer overflow is not a concern here because the maximum array size is only 1000. Empty arrays are also unnecessary to handle explicitly because the constraints guarantee at least two elements.

Worked Examples

Example 1

Input: nums = [3,2,3,2,2,2]

We first count frequencies.

Step	Current Number	Frequency Map
1	3	{3: 1}
2	2	{3: 1, 2: 1}
3	3	{3: 2, 2: 1}
4	2	{3: 2, 2: 2}
5	2	{3: 2, 2: 3}
6	2	{3: 2, 2: 4}

Now we validate frequencies:

Number	Count	Even?
3	2	Yes
2	4	Yes

Since all counts are even, the algorithm returns true.

Example 2

Input: nums = [1,2,3,4]

We count frequencies.

Step	Current Number	Frequency Map
1	1	{1: 1}
2	2	{1: 1, 2: 1}
3	3	{1: 1, 2: 1, 3: 1}
4	4	{1: 1, 2: 1, 3: 1, 4: 1}

Now we validate frequencies:

Number	Count	Even?
1	1	No

Since 1 appears an odd number of times, the algorithm immediately returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass counts frequencies, another checks counts
Space	O(n)	Hash map stores frequencies of distinct numbers

The algorithm processes the array once to build the frequency map and then iterates over distinct values to validate parity. Since both operations are linear, the overall time complexity is O(n).

The space complexity is O(n) in the worst case, when all numbers are distinct and each requires a separate hash map entry. Although values are bounded between 1 and 500, the general complexity remains linear relative to input size.

Test Cases

solution = Solution()

assert solution.divideArray([3, 2, 3, 2, 2, 2]) is True  # Provided example, valid pairing
assert solution.divideArray([1, 2, 3, 4]) is False  # Provided example, no duplicates

assert solution.divideArray([5, 5]) is True  # Minimum valid input
assert solution.divideArray([7, 8]) is False  # Minimum invalid input

assert solution.divideArray([1, 1, 2, 2, 3, 3]) is True  # Multiple valid pairs
assert solution.divideArray([1, 1, 2, 2, 3]) is False  # Odd frequency present

assert solution.divideArray([9, 9, 9, 9]) is True  # Same number repeated evenly
assert solution.divideArray([9, 9, 9]) is False  # Odd occurrence count

assert solution.divideArray([1, 1, 1, 2, 2, 2]) is False  # Multiple odd counts
assert solution.divideArray([4, 4, 4, 4, 5, 5]) is True  # Mixed frequencies, all even

assert solution.divideArray([500, 500, 1, 1]) is True  # Boundary values
assert solution.divideArray([500, 500, 500, 1, 1, 1]) is False  # Boundary with odd counts

Test	Why
[3,2,3,2,2,2]	Verifies provided valid example
[1,2,3,4]	Verifies provided invalid example
[5,5]	Tests smallest valid input
[7,8]	Tests smallest invalid input
[1,1,2,2,3,3]	Confirms multiple distinct valid pairs
[1,1,2,2,3]	Validates odd-frequency detection
[9,9,9,9]	Tests repeated identical values
[9,9,9]	Ensures odd repetition fails
[1,1,1,2,2,2]	Tests multiple odd frequencies
[4,4,4,4,5,5]	Verifies mixed even counts
[500,500,1,1]	Checks boundary values
[500,500,500,1,1,1]	Boundary values with invalid parity

Edge Cases

One important edge case is when the array contains only a single pair, such as [5,5]. A naive implementation might overcomplicate the logic or assume multiple values exist. The frequency-counting approach handles this naturally because 5 appears exactly twice, which is even.

Another critical edge case is when one number appears an odd number of times, such as [2,2,2,3,3,3]. This situation can easily introduce bugs if an implementation attempts to greedily pair elements without verifying counts globally. The frequency-based solution correctly identifies that both 2 and 3 appear three times, making pairing impossible.

A third edge case involves arrays where all values are the same, such as [8,8,8,8,8,8]. Some implementations may accidentally assume unique values or fail when repeated occurrences are very high. Since the algorithm only checks parity, it correctly determines that six occurrences can form three equal pairs.

Finally, arrays with all unique values, such as [1,2,3,4], are another common failure scenario. Since every number appears exactly once, none can be paired. The implementation quickly detects odd frequencies and returns False immediately.