Watch 10 video solutions for Divide Array Into Equal Pairs, a easy level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by NeetCodeIO has 6,020 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums consisting of 2 * n integers.
You need to divide nums into n pairs such that:
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] <= 500Problem 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 | 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 |