LeetCode 2341 - Maximum Number of Pairs in Array

The problem asks us to take an array of integers, nums, and repeatedly form pairs of equal numbers until no more pairs can be formed. Each operation removes exactly two identical numbers from the array, and we continue doing this until it is no longer possible.

leetcodeeasyarrayhash-tablecounting

LeetCode Problem 2341

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to take an array of integers, nums, and repeatedly form pairs of equal numbers until no more pairs can be formed. Each operation removes exactly two identical numbers from the array, and we continue doing this until it is no longer possible. The goal is to return a list of two integers: the total number of pairs formed and the number of integers left unpaired.

In other words, the input nums is a standard array of integers, where each integer can range from 0 to 100, and the array length ranges from 1 to 100. The output is a two-element array [pairs, leftover]. For instance, if the array contains multiple occurrences of the same number, each pair contributes to the pairs count, and any remaining single occurrences contribute to leftover.

Important edge cases include arrays with all unique elements (no pairs possible), arrays with all identical elements (maximum number of pairs), and arrays of length 1 (cannot form any pairs). The problem guarantees that the input array is non-empty and that all numbers are non-negative integers within the range [0, 100].

Approaches

The brute-force approach involves iterating through the array and repeatedly searching for duplicates to form pairs. For each element, we would search the remainder of the array for a matching number, remove both elements, and increment the pair count. While this method would eventually produce the correct result, its time complexity is poor, O(n^2), due to the repeated scanning and removals.

The optimal approach leverages a frequency count of the numbers using a hash map (dictionary in Python, map in Go). We count how many times each number appears. The number of pairs for any value is simply the integer division of its frequency by 2, and the leftover is the remainder. Summing across all numbers gives the total pairs and leftover elements. This approach reduces the time complexity to O(n) and the space complexity to O(k), where k is the range of unique numbers in the array, which is at most 101.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Scan the array repeatedly to find pairs, remove them, and count. Inefficient for larger arrays.
Optimal O(n) O(k) Use a frequency map to count occurrences and compute pairs using integer division. Efficient and simple.

Algorithm Walkthrough

  1. Initialize a frequency map (hash map or dictionary) to count occurrences of each number in nums.
  2. Iterate through the array nums. For each number, increment its count in the frequency map.
  3. Initialize two variables, pairs and leftover, to 0.
  4. For each unique number in the frequency map, calculate how many pairs can be formed using integer division count // 2 and add it to pairs.
  5. Calculate the leftover for each number using the modulo operation count % 2 and add it to leftover.
  6. Return the result as [pairs, leftover].

Why it works: Counting the occurrences ensures that we can directly compute all possible pairs without modifying the original array or performing repeated searches. Integer division gives the maximum number of pairs for each number, and modulo gives the remaining unpaired numbers. This method guarantees correctness because every pair is counted exactly once.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        freq = Counter(nums)
        pairs = 0
        leftover = 0
        
        for count in freq.values():
            pairs += count // 2
            leftover += count % 2
        
        return [pairs, leftover]

The Python implementation uses collections.Counter to efficiently count the occurrences of each number. For each count in the dictionary, count // 2 adds to the number of pairs, while count % 2 accounts for leftover numbers. Finally, we return the results as a list [pairs, leftover].

Go Solution

func numberOfPairs(nums []int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }
    
    pairs := 0
    leftover := 0
    for _, count := range freq {
        pairs += count / 2
        leftover += count % 2
    }
    
    return []int{pairs, leftover}
}

In Go, we use a map to count frequencies. Integer division / calculates the pairs, and modulo % calculates the leftovers. We then return the results as a slice of two integers. Go does not have a built-in Counter, so a standard map suffices.

Worked Examples

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

Step Frequency Map Pairs Leftover
Initial {1:2,3:2,2:3} 0 0
1 1 → count 2 → pairs +1, leftover +0 1 0
2 3 → count 2 → pairs +1, leftover +0 2 0
3 2 → count 3 → pairs +1, leftover +1 3 1
Result 3 1

Example 2: nums = [1,1]

Step Frequency Map Pairs Leftover
Initial {1:2} 0 0
1 1 → count 2 → pairs +1, leftover +0 1 0
Result 1 0

Example 3: nums = [0]

Step Frequency Map Pairs Leftover
Initial {0:1} 0 0
1 0 → count 1 → pairs +0, leftover +1 0 1
Result 0 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once to build the frequency map and then iterate through at most 101 unique keys.
Space O(k) We store a frequency map of at most 101 keys since 0 <= nums[i] <= 100.

The algorithm scales linearly with the size of the input array. The space used is minimal due to the limited range of input values.

Test Cases

# Provided examples
assert Solution().numberOfPairs([1,3,2,1,3,2,2]) == [3,1]  # multiple pairs with leftover
assert Solution().numberOfPairs([1,1]) == [1,0]            # exactly one pair
assert Solution().numberOfPairs([0]) == [0,1]              # single element, no pairs

# Additional test cases
assert Solution().numberOfPairs([1,2,3,4,5]) == [0,5]      # all unique, no pairs
assert Solution().numberOfPairs([1,1,1,1]) == [2,0]        # all identical, all paired
assert Solution().numberOfPairs([2,2,3,3,3]) == [2,1]      # mix of pairs and leftover
assert Solution().numberOfPairs([100]*100) == [50,0]       # maximum input size, all same
assert Solution().numberOfPairs([0,1,2,3,4,5,6,7,8,9]*10) == [50,0]  # uniform frequency
Test Why
[1,3,2,1,3,2,2] Mix of multiple pairs and leftover
[1,1] Single pair, no leftover
[0] Single element, no pairs
[1,2,3,4,5] All unique elements, no pairs
[1,1,1,1] All identical elements, maximum pairs
[2,2,3,3,3] Mix of pairs and leftover
[100]*100 Large input with all same numbers
[0,1,2,...,9]*10 Multiple numbers with equal frequency

Edge Cases

One important edge case is an array of length 1. Since there are no two numbers, no pairs can form. The implementation correctly counts 0 pairs and 1 leftover.

Another edge case is when all numbers are identical. The algorithm correctly calculates the maximum number of pairs using integer division and reports zero leftovers.

A third edge case is when all numbers are unique. No pairs exist, so the algorithm correctly reports zero pairs and n leftovers.

Finally, an edge case to consider is when the array contains multiple numbers with varying frequencies, including odd and even counts. The algorithm handles each frequency individually, ensuring that leftover calculation is accurate for numbers with odd occurrences.