algoadvance

Leetcode 2341. Maximum Number of Pairs in Array

Problem Statement

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:

• The number of pairs.
• The number of leftover integers that cannot be paired.

Clarifying Questions

1. What is the range of values for the integers in the input array?
   • The integers can range from a specified minimum to maximum value, as indicated by the problem constraints (commonly between -1000 and 1000).
2. Can the input array be empty?
   • If the input array is empty, the expected output should be (0, 0) since there are no elements to form pairs or have leftovers.
3. Is the output required to be a specific data type?
   • Yes, the output should be a tuple of two integers: the first being the count of pairs and the second being the count of leftover integers.

Strategy

1. Frequency Count:
   • Use an unordered map to count the frequency of each integer in the array.
2. Calculate Pairs and Leftovers:
   • Traverse through the frequency map, calculating the number of pairs that can be formed from each integer’s count.
   • A pair can be formed if the count is at least 2. For each integer, the number of pairs is the integer division of its count by 2. The leftovers will be the remainder when divided by 2.

Code

#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;
}

Time Complexity

• Time Complexity: O(n)
  • Explanation: The function traverses the 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).
• Space Complexity: O(n)
  • Explanation: The additional space used by the unordered map to store the frequencies of the elements is proportional to the number of unique elements in the array, which in the worst case can be O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?