You are given a 0-indexed integer array nums. In one operation, you may do the following:
nums that are equal.nums, forming a pair.The operation is done on nums as many times as possible.
Return a 0-indexed integer array answer of size 2 where answer[0] is the number of pairs that are formed and answer[1] is the number of leftover integers in nums after doing the operation as many times as possible.
Example 1:
Input: nums = [1,3,2,1,3,2,2] Output: [3,1] Explanation: Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2]. Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2]. Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2]. No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.
Example 2:
Input: nums = [1,1] Output: [1,0] Explanation: Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = []. No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.
Example 3:
Input: nums = [0] Output: [0,1] Explanation: No pairs can be formed, and there is 1 number leftover in nums.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100Problem Overview: You are given an integer array nums. Every pair must contain two equal numbers and each element can be used only once. The goal is to compute two values: the maximum number of valid pairs you can form and how many elements remain unused.
Approach 1: Frequency Count Approach (O(n) time, O(k) space)
This method counts how many times each number appears, then converts those counts into pairs. Iterate through the array and store frequencies in a counting structure (often an array when the value range is small). For each number with frequency f, the number of pairs is f / 2 and the leftover elements contribute f % 2. This works because every two identical values form exactly one pair. The approach runs in O(n) time since you scan the array once, and uses O(k) space where k is the value range.
This technique is common in problems involving counting and frequency analysis. When the range of values is small, a fixed-size frequency array is extremely efficient and avoids hash overhead.
Approach 2: Hash Map Solution (O(n) time, O(n) space)
When the value range is unknown or large, a hash map provides a flexible alternative. Iterate through nums and maintain a map from value to frequency. After building the map, iterate over each frequency and compute pairs using count // 2. Sum all pairs and derive leftovers using count % 2. Hash map insertions and lookups take constant average time, so the full algorithm remains O(n).
This approach is widely used in interview questions involving hash tables. The key insight is recognizing that pair formation depends only on frequency counts, not element positions in the array.
Recommended for interviews: The frequency counting solution is typically the cleanest explanation. It demonstrates that you recognize the problem as a counting task and can translate occurrences directly into pairs. Interviewers expect an O(n) approach. A brute-force pairing strategy would show basic understanding, but the frequency-based method demonstrates stronger algorithmic thinking and familiarity with hash-based counting patterns.
In this approach, we count the frequency of each number using a hash map or array. For each number, we determine how many pairs can be formed by dividing the frequency by 2. The leftover elements are the ones not used in pairs.
This C solution uses an array to count occurrences of each number. After counting, it calculates pairs and leftovers by iterating through the frequency array, using integer division and modulus.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) because the frequency array size is fixed.
This approach also involves counting frequencies, but uses a dictionary or hash map. It is particularly convenient for languages with built-in hash map support, such as Python and JavaScript.
Python's Counter class makes it easy to tally counts of each element, and the approach to calculate pairs and remaining elements is direct.
Python
JavaScript
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(n) in the worst case for storing counts.
| Approach | Complexity |
|---|---|
| Frequency Count Approach | Time Complexity: O(n) where n is the length of the array. |
| Hash Map Solution | Time Complexity: O(n) where n is the length of the array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count Approach | O(n) | O(k) | Best when value range is small and a counting array can be used |
| Hash Map Solution | O(n) | O(n) | General case when values are large or unknown |
[LeetCode Weekly Contest 302] 1 - Maximum Number of Pairs in Array • Sandeep Kumar • 1,575 views views
Watch 9 more video solutions →Practice Maximum Number of Pairs in Array with our built-in code editor and test cases.
Practice on FleetCode