Divide Array Into Equal Pairs — Problem & Solution
Divide Array Into Equal Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Divide Array Into Equal Pairs is an easy coding problem on arrays, hash table and bit manipulation, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Bit Manipulation
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums of length 2 * n.
Return true if it can be split into n pairs such that both elements of every pair are equal, and each element is used exactly once.
Example 1
Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: The pairs (2,2), (2,2) and (3,3) use every element once.
Example 2
Input: nums = [1,2,3,4]
Output: false
Explanation: Every value appears once, so no pair can be formed.
Example 3
Input: nums = [7,7]
Output: true
Constraints
nums.length is even2 <= nums.length <= 10001 <= nums[i] <= 500
Hints for Divide Array Into Equal Pairs
Hint 1
Elements can only pair with an equal value, so pairing is decided per distinct value.
Hint 2
A value with an odd count always leaves one element stranded.
Hint 3
So the whole question is whether every frequency is even.
How to solve Divide Array Into Equal Pairs
Pairs must be equal-valued, so the array splits into independent groups by value. A group of size c forms c / 2 pairs and leaves a leftover exactly when c is odd.
Approach
- Count the occurrences of every distinct value.
- If any count is odd, return
false. - Otherwise return
true.
Why it works
Necessity is clear — an odd group cannot be fully paired within itself, and cross-value pairing is forbidden. Sufficiency follows because an even group of identical values pairs off trivially.
Complexity
- Time —
O(n) - Space —
O(V) for the counts
Pitfalls
- Sorting and comparing adjacent elements works but must step by 2, not by 1.
- The XOR trick ("everything cancels to zero") is not valid here —
[1,1,2,2]and[1,2,3,0]can XOR alike for different reasons.
Reference solution
Python
from typing import List
def divideArray(nums: List[int]) -> bool:
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
for c in count.values():
if c % 2 != 0:
return False
return TrueJava
public static boolean divideArray(int[] nums) {
int[] count = new int[501];
for (int x : nums) count[x]++;
for (int c : count) {
if (c % 2 != 0) return false;
}
return true;
}C++
bool divideArray(vector<int>& nums) {
vector<int> count(501, 0);
for (int x : nums) count[x]++;
for (int c : count) {
if (c % 2 != 0) return false;
}
return true;
}JavaScript
var divideArray = function(nums) {
const count = {};
for (let i = 0; i < nums.length; i++) {
const k = String(nums[i]);
count[k] = (count[k] || 0) + 1;
}
const keys = Object.keys(count);
for (let i = 0; i < keys.length; i++) {
if (count[keys[i]] % 2 !== 0) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets