Problem

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 _a0-indexed integer array _answer of size2 whereanswer[0]is the number of pairs that are formed andanswer[1]is the number of leftover integers innums after doing the operation as many times as possible.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4

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

1
2
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

Solution

Method 1 – Counting with Hash Map

Intuition

To maximize the number of pairs, count the frequency of each number. Each pair requires two equal numbers, so the number of pairs for each value is count // 2. The leftovers are the numbers that couldn’t be paired.

Approach

  1. Count the frequency of each number in the array using a hash map.
  2. For each number, add count // 2 to the total pairs and count % 2 to the leftovers.
  3. Return the total pairs and leftovers as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        int pairs = 0, left = 0;
        for (auto& [k, v] : cnt) {
            pairs += v / 2;
            left += v % 2;
        }
        return {pairs, left};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numberOfPairs(nums []int) []int {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }
    pairs, left := 0, 0
    for _, v := range cnt {
        pairs += v / 2
        left += v % 2
    }
    return []int{pairs, left}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int[] numberOfPairs(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        int pairs = 0, left = 0;
        for (int v : cnt.values()) {
            pairs += v / 2;
            left += v % 2;
        }
        return new int[]{pairs, left};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numberOfPairs(nums: IntArray): IntArray {
        val cnt = mutableMapOf<Int, Int>()
        for (x in nums) cnt[x] = cnt.getOrDefault(x, 0) + 1
        var pairs = 0
        var left = 0
        for (v in cnt.values) {
            pairs += v / 2
            left += v % 2
        }
        return intArrayOf(pairs, left)
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfPairs(self, nums: list[int]) -> list[int]:
        from collections import Counter
        cnt = Counter(nums)
        pairs = left = 0
        for v in cnt.values():
            pairs += v // 2
            left += v % 2
        return [pairs, left]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use std::collections::HashMap;
impl Solution {
    pub fn number_of_pairs(nums: Vec<i32>) -> Vec<i32> {
        let mut cnt = HashMap::new();
        for x in nums {
            *cnt.entry(x).or_insert(0) += 1;
        }
        let mut pairs = 0;
        let mut left = 0;
        for &v in cnt.values() {
            pairs += v / 2;
            left += v % 2;
        }
        vec![pairs, left]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    numberOfPairs(nums: number[]): number[] {
        const cnt = new Map<number, number>();
        for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
        let pairs = 0, left = 0;
        for (const v of cnt.values()) {
            pairs += Math.floor(v / 2);
            left += v % 2;
        }
        return [pairs, left];
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, since we count each number once.
  • 🧺 Space complexity: O(n), for the hash map storing counts.