2341. Maximum Number of Pairs in Array
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 innums
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 originalnums
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.
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 aCounter
. - 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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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]
.
-
First, we create a frequency counter for
nums
using theCounter
class. This results in the following counts of each number:4: 2
5: 2
6: 3
-
Next, we iterate over these counts to determine the number of pairs we can form:
- For number
4
, count is2
. Number of pairs formed2 // 2 = 1
. - For number
5
, count is2
. Number of pairs formed2 // 2 = 1
. - For number
6
, count is3
. Number of pairs formed3 // 2 = 1
(with1
leftover).
- For number
-
We sum up the number of pairs. So,
1 (from 4) + 1 (from 5) + 1 (from 6) = 3
. Thus, the total number of pairss
is3
. -
We then need to find the number of leftover integers. There are
7
original numbers innums
, and after forming3
pairs (which includes6
numbers), we subtract6
from7
:- Leftover integers:
7 - 3 * 2 = 1
.
- Leftover integers:
-
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
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.
-
Constructing the counter
cnt
fromnums
has a time complexity ofO(n)
, wheren
is the length of the input listnums
. This is becauseCounter
goes through each element in the list once. -
Iterating over the values of the counter
cnt
to calculate the sum takesO(k)
, wherek
is the number of unique elements innums
. In the worst case, if all elements are distinct,k
is equal ton
.
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
.
-
The counter
cnt
can store at mostk
key-value pairs, wherek
is the number of unique elements innums
. In the worst case, the space complexity would thus beO(k)
. -
The list
nums
itself is not modified, and no additional space that is dependent onn
is used beyond the countercnt
.
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.
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
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.