Skip to main content
Talentd

Maximum Number of Pairs in Array - Solution & Explanation

EasyArrayHash TableCounting18 min readAsked at: Altimetrik
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums. In one operation, you may do the following:

  • Choose two integers in nums that are equal.
  • Remove both integers from 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 <= 100
  • 0 <= nums[i] <= 100

Approach Overview

Problem 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.

Approach 1: Frequency Count Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) because the frequency array size is fixed.

Try this approach in the editor →

Approach 2: Hash Map Solution

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(n) in the worst case for storing counts.

Try this approach in the editor →

Approach 3: Counting

We can count the occurrences of each number x in the array nums and record them in a hash table or array cnt.

Then, we traverse cnt. For each number x, if the occurrence count v of x is greater than 1, we can select two x's from the array to form a pair. We divide v by 2 and take the floor value to get the number of pairs that can be formed by the current number x. We then add this number to the variable s.

The remaining count is the length of the array nums minus the number of pairs formed multiplied by 2, i.e., n - s times 2.

The answer is [s, n - s times 2].

The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the array nums, and C is the range of numbers in the array nums, which is 101 in this problem.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#C

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency Count Approach

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) because the frequency array size is fixed.

Hash Map Solution

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(n) in the worst case for storing counts.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count ApproachO(n)O(k)Best when value range is small and a counting array can be used
Hash Map SolutionO(n)O(n)General case when values are large or unknown

Video Solution

[LeetCode Weekly Contest 302] 1 - Maximum Number of Pairs in Array • Sandeep Kumar • 1,583 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Pairs in Array easy or hard?
Maximum Number of Pairs in Array is classified as an Easy problem. The challenge mainly tests whether you recognize that pair formation depends on frequency counts rather than element positions.
Maximum Number of Pairs in Array Python/Java solution
In Python, the solution commonly uses collections.Counter or a dictionary to count frequencies. In Java, a HashMap or an integer frequency array is used. Both implementations iterate through the array and compute pairs using integer division.
How to solve Maximum Number of Pairs in Array in O(n)?
Iterate through the array and track the frequency of each number using a counting array or hash map. For each value with frequency f, compute pairs as f // 2 and leftover elements as f % 2. Summing these values gives the final result in linear time.
What is the best approach for Maximum Number of Pairs in Array?
The best approach uses frequency counting. Count how many times each number appears, then compute pairs using count // 2 and leftovers using count % 2. This runs in O(n) time and requires O(k) space for the frequency structure.
Is Maximum Number of Pairs in Array asked at Google/Amazon/Meta?
Pair counting and frequency-based problems appear frequently in interviews at companies like Amazon and Google. The exact LeetCode problem may vary, but the pattern of using hash maps or counting arrays to convert frequencies into pairs is a common interview concept.
What data structure is used in Maximum Number of Pairs in Array?
The problem is typically solved using a hash table or a frequency counting array. Both structures track how many times each number appears, allowing pairs to be computed directly from the counts.
What is the time complexity of Maximum Number of Pairs in Array?
The optimal solution runs in O(n) time because the array is scanned once to count frequencies. Calculating pairs from the counts takes O(k), which is small compared to n. Space complexity is O(k) for a counting array or O(n) for a hash map.

Ready to solve this problem?

Practice Maximum Number of Pairs in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort Array by Increasing Frequency

Next

Sort Characters By Frequency