2341. Maximum Number of Pairs in Array

Problem Description

Given a 0-indexed integer array nums, you can perform an operation where you choose two equal integers in nums and remove them, forming a pair. The goal is to determine the maximum number of pairs that can be formed and the number of leftover integers. The solution should return a 0-indexed integer array answer of size 2, where answer[0] is the number of pairs and answer[1] is the number of leftover integers.

Solution: Counting

The most efficient approach is to use a counting method. We can count the occurrences of each number in the input array nums. Then, for each number, we can determine how many pairs can be formed by dividing its count by 2 (integer division). The sum of these pairs across all numbers gives us the total number of pairs. The remaining elements are those whose counts were odd after forming pairs.

Algorithm

1. Count Occurrences: Create a hash table (or an array if the range of numbers is small) to store the frequency of each number in nums.
2. Calculate Pairs: Iterate through the frequencies. For each number's frequency count, calculate the number of pairs that can be formed using integer division (count // 2). Sum up these pair counts to get the total number of pairs.
3. Calculate Leftovers: The number of leftovers is the total number of elements minus twice the total number of pairs.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of nums. This is because we iterate through the array once to count occurrences and then iterate through the counts (which is at most the number of unique elements).
• Space Complexity: O(C), where C is the range of numbers in nums. In this problem, C is at most 101 (0 to 100), making the space complexity effectively constant. If the range of numbers were much larger, the space complexity would depend on the number of unique elements.

Code Implementation

Python

from collections import Counter
 
class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        counts = Counter(nums)
        pairs = sum(count // 2 for count in counts.values())
        leftovers = len(nums) - 2 * pairs
        return [pairs, leftovers]
 

Java

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int[] numberOfPairs(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        int pairs = 0;
        for (int count : counts.values()) {
            pairs += count / 2;
        }
        int leftovers = nums.length - 2 * pairs;
        return new int[] {pairs, leftovers};
    }
}

C++

#include <vector>
#include <map>
 
using namespace std;
 
class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        map<int, int> counts;
        for (int num : nums) {
            counts[num]++;
        }
        int pairs = 0;
        for (auto const& [key, val] : counts) {
            pairs += val / 2;
        }
        int leftovers = nums.size() - 2 * pairs;
        return {pairs, leftovers};
    }
};

Other Languages: The same algorithmic approach can be easily adapted to other programming languages like JavaScript, Go, C#, etc., maintaining the same time and space complexity. The core idea of counting occurrences and calculating pairs and leftovers remains consistent.