2341. Maximum Number of Pairs in Array

EasyArrayHash TableCounting
Leetcode Link

Problem Description

The problem presents you with an array of integers called nums and asks you to perform a series of operations on this array. In each operation, you must:

  • Find two identical numbers in the array.
  • Remove those two identical numbers from the array to form a 'pair'.

You continue performing this operation until it is no longer possible (i.e., there are no more identical numbers to pair up). The output is an array answer of size 2, where:

  • answer[0] is the total number of pairs you have formed.
  • answer[1] is the remaining number of integers left in nums after pairing up as much as you can.

The challenge is to calculate these two values efficiently.

Intuition

To find the solution to this problem, understanding the frequency of each number in the array is crucial. Two equal integers can form a pair, which means we need to count how often each integer appears in the array. The most straightforward approach is to use a frequency counter, which is a common method to store the number of occurrences of each element in a collection (like a list). This can be achieved elegantly in Python using the Counter class from the collections module. Once we have the counter, we can iterate through the values of this frequency counter:

  • For each number in the counter, the number of pairs that can be formed is equal to frequency of the number // 2. We use integer division here because we can only form a whole pair of numbers; any extra would remain unpaired.
  • We sum all these whole pairs to get the total number of pairs formed.
  • To find out the number of leftover integers, we can sum the contributions of the leftover from each number by considering frequency of the number % 2 (the remainder of the number of each integer when divided by 2). Since this can be a bit inefficient, we can also use the length of the original nums array and subtract twice the number of pairs formed (since each pair is made up of two numbers).

Using the Counter and these basic arithmetic operations allows us to arrive at the solution efficiently and accurately.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The solution utilizes a Counter from Python's collections module to efficiently count the frequency of each number in the input nums array. By doing so, we create a data structure that maps each unique number to the number of times it appears in the array. This mapping is essential for understanding how many pairs we can form.

Once we have the Counter, the solution iterates over the values (which represent the count of occurrences of each number). For each count, it calculates the number of whole pairs that can be formed by that specific number using integer division //. Integer division by 2 gives us the number of pairs because it takes two identical integers to form one pair, and any excess number cannot form a pair on its own.

The pairs are then summed to get the total number of pairs formed which is represented by s in the solution code. This sum s is given by the expression sum(v // 2 for v in cnt.values()). Here cnt is the Counter for nums, v is each count value for the numbers in cnt, and the sum is over the number of pairs (integer division of v by 2).

After calculating the total sum of pairs, we need to determine the remaining unpaired integers. We can do this by subtracting twice the number of pairs from the total length of nums, because for every pair, two elements are removed from the array. This subtraction is done in the return statement return [s, len(nums) - s * 2]. The result is a list where the first element is the number of pairs s, and the second element is the number of leftover integers len(nums) - s * 2.

To summarize, the algorithm can be broken down into the following steps:

  • Count the frequency of each unique integer in nums using a Counter.
  • Calculate the number of pairs by summing up the integer division by 2 of each count in the Counter.
  • Determine the leftover integers by subtracting twice the number of pairs from the original list's length.
  • Return the number of pairs and the number of leftover integers as a list.

This approach is efficient as it only requires one pass over the data to create the Counter, and then another pass over the unique elements (the keys of the Counter) to calculate pairs. This results in a time complexity of O(n) where n is the number of elements in nums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's use a small example to illustrate how the solution approach works. Suppose the input array nums is [4, 5, 6, 4, 5, 6, 6].

  1. First, we create a frequency counter for nums using the Counter class. This results in the following counts of each number:

    • 4: 2
    • 5: 2
    • 6: 3

  2. Next, we iterate over these counts to determine the number of pairs we can form:

    • For number 4, count is 2. Number of pairs formed 2 // 2 = 1.
    • For number 5, count is 2. Number of pairs formed 2 // 2 = 1.
    • For number 6, count is 3. Number of pairs formed 3 // 2 = 1 (with 1 leftover).

  3. We sum up the number of pairs. So, 1 (from 4) + 1 (from 5) + 1 (from 6) = 3. Thus, the total number of pairs s is 3.

  4. We then need to find the number of leftover integers. There are 7 original numbers in nums, and after forming 3 pairs (which includes 6 numbers), we subtract 6 from 7:

    • Leftover integers: 7 - 3 * 2 = 1.

  5. The result is returned as a list where the first element is the number of pairs, and the second element is the number of leftover integers. For this example, it would be [3, 1].

In conclusion, the solution approach correctly determines that from the input array [4, 5, 6, 4, 5, 6, 6], we can form 3 pairs and we are left with 1 unpaired integer. The final answer is [3, 1].

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def numberOfPairs(self, nums: List[int]) -> List[int]:
5        # Create a counter for all elements in the nums list
6        num_counter = Counter(nums)
7      
8        # Calculate pairs by summing the integer division of counts by 2
9        # This gives us the number of pairs for each unique number
10        pairs = sum(count // 2 for count in num_counter.values())
11      
12        # Return the number of pairs and the number of leftover elements 
13        # Leftovers are calculated by subtracting twice the number of pairs from the total number of elements
14        return [pairs, len(nums) - pairs * 2]
15
16# Comment:
17# The numberOfPairs method takes a list of integers (`nums`) and returns a list 
18# where the first element is the number of pairs that can be formed and the second 
19# element is the number of elements that cannot be paired.
20
1class Solution {
2  
3    public int[] numberOfPairs(int[] nums) {
4        // Create an array to count occurrences of each number, assuming the given range is 0-100
5        int[] count = new int[101]; 
6      
7        // Count the number of times each number appears in the input array
8        for (int num : nums) { 
9            ++count[num]; // Increment the count for the current number
10        }
11      
12        // Initialize a variable to keep track of the total number of pairs
13        int totalPairs = 0; 
14      
15        // Calculate the number of pairs for each number and add to the totalPairs
16        for (int occurrences : count) { 
17            totalPairs += occurrences / 2; // A pair is two of the same number, hence we divide by 2
18        }
19      
20        // The total number of leftovers is the original array size minus twice the number of pairs
21        int leftovers = nums.length - totalPairs * 2; 
22      
23        // Return an array containing the total number of pairs and the leftovers
24        return new int[] {totalPairs, leftovers}; 
25    }
26}
27
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to find the number of pairs that can be made in the vector nums
7    vector<int> numberOfPairs(vector<int>& nums) {
8        // Initialize a vector to hold the count of each number up to 100
9        vector<int> count(101, 0);
10      
11        // Increment the count for each number in the input vector
12        for (int num : nums) {
13            ++count[num];
14        }
15      
16        // Initialize the number of pairs to zero
17        int pairs = 0;
18      
19        // Count the number of pairs for each count value
20        for (int frequency : count) {
21            pairs += frequency / 2; // Each pair requires two of the same number
22        }
23      
24        // Calculate the number of leftover elements by subtracting the
25        // number of elements forming pairs (pairs * 2) from the total number of elements
26        int leftovers = static_cast<int>(nums.size()) - pairs * 2;
27      
28        // Return the number of pairs and leftovers as a vector of two elements
29        return {pairs, leftovers};
30    }
31};
32
1// Function takes an array of numbers and returns the number of pairs 
2// along with the number of leftover elements after pairing them.
3function numberOfPairs(nums: number[]): number[] {
4    // Get the length of the array.
5    const lengthOfNums = nums.length;
6    // Initialize an array to keep a count of each number (up to 100 as per the constraint).
7    // If the constraints change, this upper limit should be updated accordingly.
8    const counts = new Array(101).fill(0);
9    // Iterate through the 'nums' array and count occurrences of each number.
10    for (const num of nums) {
11        counts[num]++;
12    }
13    // Calculate the sum of pairs by adding half the count of each number 
14    // (using bitwise right shift to quickly divide by 2).
15    const totalPairs = counts.reduce((runningTotal, currentCount) => runningTotal + (currentCount >> 1), 0);
16    // Calculate the remaining number of elements after forming pairs.
17    const remainingElements = lengthOfNums - totalPairs * 2;
18    // Return the total number of pairs and the remaining elements.
19    return [totalPairs, remainingElements];
20}
21
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The time complexity of the function primarily depends on two operations: the construction of the counter cnt and the subsequent iteration over its values to sum the number of pairs.

  1. Constructing the counter cnt from nums has a time complexity of O(n), where n is the length of the input list nums. This is because Counter goes through each element in the list once.

  2. Iterating over the values of the counter cnt to calculate the sum takes O(k), where k is the number of unique elements in nums. In the worst case, if all elements are distinct, k is equal to n.

Therefore, the overall time complexity of the function is O(n + k). However, since k <= n, we can simplify this to O(n).

Space Complexity

The space complexity is determined by the space required to store the counter cnt.

  1. The counter cnt can store at most k key-value pairs, where k is the number of unique elements in nums. In the worst case, the space complexity would thus be O(k).

  2. The list nums itself is not modified, and no additional space that is dependent on n is used beyond the counter cnt.

Assuming the unique elements in nums are bounded by n, the space complexity can be simplified to O(n), which accounts for the space required to store the counter for each unique element in the list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫