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:

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

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