Leetcode 2341. Maximum Number of Pairs in Array
Given an array of integers nums
, return the maximum number of pairs that can be formed using the integers from the array. Each pair consists of two equal integers. The function should return a tuple of two values:
(0, 0)
since there are no elements to form pairs or have leftovers.#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
pair<int, int> numberOfPairs(vector<int>& nums) {
unordered_map<int, int> frequency;
// Step 1: Calculate frequency of each number
for(int num : nums) {
frequency[num]++;
}
int pairs = 0;
int leftovers = 0;
// Step 2: Calculate pairs and leftovers
for(const auto& entry : frequency) {
pairs += entry.second / 2;
leftovers += entry.second % 2;
}
return {pairs, leftovers};
}
int main() {
vector<int> nums = {1,3,2,1,3,2,2};
pair<int, int> result = numberOfPairs(nums);
cout << "Pairs: " << result.first << ", Leftovers: " << result.second << endl;
return 0;
}
nums
array once to compute the frequency of each element, taking O(n) time. Then, it traverses the frequency map which has at most n unique elements, also taking O(n) time. Hence, the overall time complexity is O(n).Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?