Maximum Number of Pairs in Array — Problem & Solution
Maximum Number of Pairs in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Number of Pairs in Array is an easy coding problem on arrays, hash table and counting, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting
- 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
Repeatedly remove two equal elements from nums and form a pair, until no two equal elements remain.
Return [pairs, leftovers] — the number of pairs formed and the number of elements still in the array.
Example 1
Input: nums = [1,3,2,1,3,2,2]
Output: [3,1]
Explanation: Three pairs (1,1), (3,3), (2,2) leave a single 2.
Example 2
Input: nums = [1,1]
Output: [1,0]
Example 3
Input: nums = [0]
Output: [0,1]
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 100
Hints for Maximum Number of Pairs in Array
Hint 1
Pairs can only form between equal values, so handle each value independently.
Hint 2
A value occurring
ctimes contributesc / 2pairs andc % 2leftovers.Hint 3
Sum both across all distinct values.
How to solve Maximum Number of Pairs in Array
Pairing never crosses value boundaries, so the array splits into independent groups and each group's answer is a division and a remainder.
Approach
- Count the occurrences of each value.
- Add
count / 2to the pair total andcount % 2to the leftover total. - Return both.
Why it works
Within a group of c identical elements, greedy pairing removes two at a time and leaves c mod 2 behind — and no ordering of removals can do better, since every pair uses exactly two.
Complexity
- Time —
O(n) - Space —
O(V)
Pitfalls
- Computing leftovers as
n - 2 * pairsalso works, but only ifpairswas summed correctly first. - Simulating the removals is fine here but pointlessly slower.
Reference solution
Python
from typing import List
def numberOfPairs(nums: List[int]) -> List[int]:
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
pairs = sum(c // 2 for c in count.values())
left = sum(c % 2 for c in count.values())
return [pairs, left]Java
public static int[] numberOfPairs(int[] nums) {
int[] count = new int[101];
for (int x : nums) count[x]++;
int pairs = 0, left = 0;
for (int v = 0; v <= 100; v++) {
pairs += count[v] / 2;
left += count[v] % 2;
}
return new int[] { pairs, left };
}C++
vector<int> numberOfPairs(vector<int>& nums) {
vector<int> count(101, 0);
for (int x : nums) count[x]++;
int pairs = 0, left = 0;
for (int v = 0; v <= 100; v++) {
pairs += count[v] / 2;
left += count[v] % 2;
}
return { pairs, left };
}JavaScript
var numberOfPairs = function(nums) {
const count = new Array(101).fill(0);
for (let i = 0; i < nums.length; i++) count[nums[i]]++;
let pairs = 0, left = 0;
for (let v = 0; v <= 100; v++) {
pairs += Math.floor(count[v] / 2);
left += count[v] % 2;
}
return [pairs, left];
};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