#2206

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Divide Array Into Equal Pairs

Determine if an array of 2n integers can be partitioned into n pairs where each pair contains identical elements using hash counting.

array hash table bit manipulation counting

Problem Statement

You are given an integer array nums containing 2 * n elements. Your task is to determine whether it is possible to divide nums into n pairs such that each pair consists of two identical numbers.

Return true if such a division exists, otherwise return false. For example, nums = [3,2,3,2,2,2] can be paired as (2,2), (3,3), and (2,2), satisfying the condition, while nums = [1,2,3,4] cannot form valid pairs.

Examples

Example 1

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

Output: true

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

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 <= n <= 500
1 <= nums[i] <= 500

Solution Approach

Count occurrences with a hash map

Iterate through nums and store the frequency of each number in a hash map. This helps track how many elements are available for pairing, which is central to the array scanning plus hash lookup pattern.

Verify even counts for all numbers

After counting, check that every number has an even frequency. Any odd frequency indicates an element cannot form a complete pair, immediately returning false.

Return result based on counts

If all numbers have even counts, return true since all elements can be paired. This completes the O(n) solution with direct reliance on hash counting and array scanning.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because we scan nums once to build counts and then iterate over the hash map. Space complexity is O(n) due to the hash map storing frequencies of elements.

What Interviewers Usually Probe

Expect fast hashing to track occurrences for a simple O(n) solution.
Check for edge cases where some numbers appear an odd number of times.
Look for direct application of array scanning plus hash lookup rather than sorting.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle odd frequencies correctly, which causes wrong true results.
Assuming sorted pairing is needed, which adds unnecessary complexity.
Ignoring the problem constraint that nums length is always even.

Follow-up variants

Pair array elements into groups of k instead of 2, generalizing the hash counting approach.
Determine if all elements can be paired when allowed to swap any numbers arbitrarily.
Return the actual pairs formed instead of only a boolean, still using frequency counts.

FAQ

What is the core pattern in Divide Array Into Equal Pairs?

The core pattern is array scanning plus hash lookup, where element frequencies determine if valid pairs can be formed.

Can sorting nums help in this problem?

Sorting is unnecessary; using a hash map for frequency counting is faster and avoids O(n log n) overhead.

How does GhostInterview ensure correctness?

It simulates counting for each number and verifies all counts are even, immediately flagging any odd occurrences.

What are edge cases to watch for?

Arrays where a single number occurs an odd number of times or when all numbers are identical, both affecting pair formation.

What is the time and space complexity?

Time is O(n) for scanning and counting, space is O(n) for the hash map storing frequencies of elements.

terminal

Solution

Solution 1: Counting

According to the problem description, as long as each element in the array appears an even number of times, the array can be divided into $n$ pairs.

1

2

3

4

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        cnt = Counter(nums)
        return all(v % 2 == 0 for v in cnt.values())

Continue Practicing

#2275 largest combination with bitwise and greater than zero #1994 the number of good subsets #2506 count pairs of similar strings