Difficulty: Easy | Acceptance: 76.10% | Paid: No Topics: Array, Hash Table, Counting
You are given a 0-indexed integer array nums. In one operation, you may do the following:
Choose two integers from nums that are equal. Remove both integers from nums, forming a pair.
The operation is done until no more pairs can be formed.
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.
- Examples
- Constraints
- Sorting Approach
- Hash Map Frequency Count
- Set Approach
Examples
Input: nums = [1,3,2,1,3,2,2]
Output: [3,1]
Explanation:
- Remove the pair [1,1] from nums, resulting in nums = [3,2,3,2,2].
- Remove the pair [3,3] from nums, resulting in nums = [2,2,2].
- Remove the pair [2,2] from nums, resulting in nums = [2].
No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.
Input: nums = [1,1]
Output: [1,0]
Explanation: Remove the pair [1,1] from nums, resulting in nums = [].
No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.
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
Sorting Approach
Intuition By sorting the array, equal numbers become adjacent, making it easy to count consecutive pairs.
Steps
- Sort the array in ascending order
- Iterate through the sorted array
- When two consecutive elements are equal, increment pair count and skip both
- Otherwise, move to the next element
- Calculate leftovers as total elements minus 2 times pairs
from typing import List
class Solution:
def numberOfPairs(self, nums: List[int]) -> List[int]:
nums.sort()
pairs = 0
i = 0
n = len(nums)
while i < n:
if i + 1 < n and nums[i] == nums[i + 1]:
pairs += 1
i += 2
else:
i += 1
leftovers = n - 2 * pairs
return [pairs, leftovers]Complexity
- Time: O(n log n) due to sorting
- Space: O(1) or O(n) depending on sorting implementation
- Notes: Simple but not optimal due to sorting overhead
Hash Map Frequency Count
Intuition Count the frequency of each number, then calculate pairs and leftovers directly from the frequencies.
Steps
- Build a frequency map of all numbers
- For each unique number, add frequency // 2 to pairs
- Add frequency % 2 to leftovers
- Return the result array
from typing import List
from collections import Counter
class Solution:
def numberOfPairs(self, nums: List[int]) -> List[int]:
freq = Counter(nums)
pairs = 0
leftovers = 0
for count in freq.values():
pairs += count // 2
leftovers += count % 2
return [pairs, leftovers]Complexity
- Time: O(n) for single pass through array and map
- Space: O(n) for the frequency map
- Notes: Optimal time complexity with clear logic
Set Approach
Intuition Use a set to track unpaired numbers. When encountering a number already in the set, we found a pair.
Steps
- Initialize an empty set to track unpaired numbers
- For each number in the array:
- If number exists in set, remove it and increment pair count
- Otherwise, add the number to the set
- Leftovers equals the size of the set
- Return the result array
from typing import List
class Solution:
def numberOfPairs(self, nums: List[int]) -> List[int]:
seen = set()
pairs = 0
for num in nums:
if num in seen:
seen.remove(num)
pairs += 1
else:
seen.add(num)
leftovers = len(seen)
return [pairs, leftovers]Complexity
- Time: O(n) for single pass through array
- Space: O(n) for the set in worst case
- Notes: Elegant solution with constant-time set operations