#2341

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Number of Pairs in Array

Given an array, count how many pairs can be formed and how many leftovers remain after pairing.

Problem Statement

You are given a 0-indexed integer array nums. In one operation, you can form a pair from two equal integers and remove them from the array. Repeat the operation as many times as possible.

Return an integer array of size 2 where the first element is the number of pairs that can be formed, and the second element is the number of leftover integers after performing the operations.

Examples

Example 1

Input: nums = [1,3,2,1,3,2,2]

Output: [3,1]

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]

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]

No pairs can be formed, and there is 1 number leftover in nums.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

Solution Approach

Counting Frequencies

The first step is to count the frequency of each integer in the array. Using a hash table (or dictionary), you can efficiently store and retrieve the count of each number. This allows us to know how many pairs we can form from each number.

Forming Pairs

Once the frequencies are known, the next step is to determine how many pairs can be formed. Each pair requires two of the same number, so the number of pairs from each number is determined by integer division of its frequency by 2.

Calculating Leftovers

After forming pairs, the leftover integers are the ones that couldn’t be paired. This is simply the sum of the remainders when dividing the frequency of each integer by 2.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the final approach, but counting the frequencies takes O(n) time. Forming pairs and calculating leftovers also take O(n) time, making the overall time complexity O(n), where n is the length of the array. Space complexity is O(k), where k is the number of unique integers in the array, due to the hash table used for counting frequencies.

What Interviewers Usually Probe

Can the candidate identify the necessity of counting frequencies to determine pairs?
How well does the candidate handle hashing and array scanning in their solution?
Is the candidate aware of how to efficiently calculate leftovers after pairing?

Common Pitfalls or Variants

Common pitfalls

Overlooking the need to count frequencies before trying to form pairs.
Forgetting to account for leftover integers after forming pairs.
Not using a hash table or efficient data structure for counting, which leads to poor performance.

Follow-up variants

What if the array contains negative numbers?
How would the solution change if duplicates can be paired multiple times?
What if we are asked to find pairs with different conditions, such as pairs whose sum equals a target?

FAQ

What is the primary pattern used to solve the Maximum Number of Pairs in Array problem?

The primary pattern is array scanning plus hash lookup. You count the frequency of each number and then form pairs based on those frequencies.

How can I optimize my solution for this problem?

Using a hash table to store the frequency of each number allows for efficient counting, and the overall solution can be done in linear time.

What happens if there are no pairs to form?

If no pairs can be formed, the result will be 0 pairs and the array will have all its elements as leftovers.

Can this problem be solved with sorting?

Sorting could work, but it would be less efficient. Using a hash table for counting is typically faster.

What is the space complexity of the solution?

The space complexity is O(k), where k is the number of unique integers in the array, due to the hash table storing frequencies.

terminal

Solution

Solution 1: Counting

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

1

2

3

4

5

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        cnt = Counter(nums)
        s = sum(v // 2 for v in cnt.values())
        return [s, len(nums) - s * 2]

Continue Practicing

#2347 best poker hand #2364 count number of bad pairs #2284 sender with largest word count