Divide Array Into Equal Pairs - Solution & Explanation
Problem Statement
You are given an integer array nums consisting of 2 * 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 * n1 <= n <= 5001 <= nums[i] <= 500
Approach Overview
Problem Overview: You are given an integer array with an even number of elements. The task is to check whether the array can be divided into pairs such that both elements in every pair are equal. In practice, this means every value in the array must appear an even number of times.
Approach 1: Frequency Count Approach (O(n) time, O(n) space)
This approach counts how many times each number appears using a hash-based frequency table. Iterate through the array once and increment the count for each value. After building the frequency map, iterate over the stored counts and verify that every frequency is even. If any value has an odd frequency, forming equal pairs becomes impossible.
The key insight: each pair consumes exactly two identical elements. A value appearing 2k times can form k valid pairs, but a value appearing 2k + 1 times leaves one element unmatched. Hash lookups and updates are constant time, so the overall complexity stays linear. This approach relies on a hash table and simple counting, making it the most direct and scalable solution for unsorted arrays.
Approach 2: Sorting Approach (O(n log n) time, O(1) or O(n) space)
Another strategy sorts the array first, grouping identical numbers together. After sorting, iterate through the array in steps of two. For each step, compare nums[i] with nums[i+1]. If the two values differ, the array cannot be partitioned into equal pairs.
Sorting ensures duplicates appear next to each other, which simplifies verification. This method uses a common array technique: sequential pair comparison after ordering elements. While the logic is straightforward, sorting introduces an O(n log n) time cost. Space complexity depends on the sorting algorithm—some languages use in-place sorting with O(1) extra space, while others allocate additional buffers.
Recommended for interviews: The frequency count approach is the expected solution. Interviewers typically want to see that you recognize the parity constraint—each number must appear an even number of times. Implementing it with a hash map shows familiarity with counting patterns and constant-time lookups. The sorting approach is still valid and demonstrates problem-solving flexibility, but the linear-time hash counting solution better highlights algorithmic efficiency.
Approach 1: Frequency Count Approach
This approach involves counting the frequency of each number in the array. If all frequencies are even, then it is possible to pair the numbers; otherwise, it is not.
The solution creates a frequency count array `count` where each index corresponds to a number in `nums`. As it iterates through `nums`, it increments the frequency for each number. Finally, it checks all frequencies to ensure they're even, which is necessary for perfect pairing. If any frequency is odd, it returns `false`; otherwise, `true`.
Complexity
Time Complexity: O(n), where n is numsSize. Space Complexity: O(1), since the frequency array size is fixed and independent of input size.
Approach 2: Sorting Approach
This approach involves sorting the array and then checking adjacent elements in pairs. If all pairs are identical, then the array can be divided into equal pairs.
The C solution sorts the array using `qsort` and then compares every adjacent pair for equality. If any pair is not equal, `false` is returned.
Complexity
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if the sort is in-place.
Approach 3: 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.
Therefore, we can use a hash table or an array cnt to record the number of occurrences of each element, then traverse cnt. If any element appears an odd number of times, return false; otherwise, return true.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
Rust
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n), where n is numsSize. Space Complexity: O(1), since the frequency array size is fixed and independent of input size. |
| Sorting Approach | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if the sort is in-place. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count (Hash Map) | O(n) | O(n) | General case when the array is unsorted and you want the optimal linear-time solution |
| Sorting + Pair Check | O(n log n) | O(1) to O(n) | Useful when sorting is already required elsewhere or when avoiding extra hash structures |
Video Solution
Divide Array Into Equal Pairs - Leetcode 2206 - Python • NeetCodeIO • 6,144 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Divide Array Into Equal Pairs easy or hard?
Divide Array Into Equal Pairs Python/Java solution
How to solve Divide Array Into Equal Pairs in O(n)?
What is the best approach for Divide Array Into Equal Pairs?
Is Divide Array Into Equal Pairs asked at Google/Amazon/Meta?
What data structure is used in Divide Array Into Equal Pairs?
What is the time complexity of Divide Array Into Equal Pairs?
Ready to solve this problem?
Practice Divide Array Into Equal Pairs with our built-in code editor and test cases.
Practice on FleetCode