algoadvance

Leetcode 2341. Maximum Number of Pairs in Array

Problem Statement

You are given a 0-indexed integer array nums. In one operation, you may do the following:

• Choose two integers in nums that are equal.
• Remove both integers from nums, forming a pair.

The operation is done repeatedly until no more pairs can be formed.

Return a 0-indexed integer array answer of size 2 where answer[0] is the number of pairs that are formed, and answer[1] is the number of leftover integers in nums after all possible pairs are formed.

Clarifying Questions

1. Q: Are the pairs required to be adjacent in the array? A: No, pairs can be formed from any two equal integers in the array regardless of their positions.
2. Q: What if the input array nums is empty? A: If nums is empty, the result should be [0, 0] because no pairs can be formed and there are no leftover elements.
3. Q: Will there always be an even number of same integers to form pairs? A: Not necessarily. Leftover integers are possible if there are odd counts of some integers.

Strategy

1. Counting Frequency:
   • Use a HashMap to count the frequency of each integer in the array.
2. Calculating Pairs and Leftovers:
   • Iterate through the frequency map.
   • For each integer, calculate how many pairs can be formed (count // 2).
   • Calculate the number of leftover elements (count % 2).
3. Aggregate Results:
   • Sum up the total number of pairs.
   • Sum up the total number of leftover elements.

Code

import java.util.HashMap;
import java.util.Map;

public class MaximumNumberOfPairs {

    public int[] numberOfPairs(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        
        // Counting frequency of each number
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        int pairs = 0;
        int leftovers = 0;
        
        // Calculating pairs and leftovers
        for (int count : countMap.values()) {
            pairs += count / 2;
            leftovers += count % 2;
        }
        
        return new int[] { pairs, leftovers };
    }

    public static void main(String[] args) {
        MaximumNumberOfPairs solver = new MaximumNumberOfPairs();
        
        int[] nums1 = {1,2,3,4,5,6};
        int[] nums2 = {1,1,2,2,3,3};
        int[] nums3 = {1,1,1,1,1};
        
        // Testing the function
        System.out.println(Arrays.toString(solver.numberOfPairs(nums1))); // Output: [0, 6]
        System.out.println(Arrays.toString(solver.numberOfPairs(nums2))); // Output: [3, 0]
        System.out.println(Arrays.toString(solver.numberOfPairs(nums3))); // Output: [2, 1]
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of integers in the array nums. We are iterating through the array once to populate the frequency map and then iterating through the map which contains at most n unique keys.
• Space Complexity: O(n), where n is the number of integers in the array nums, in the worst case, the map might have n entries if all elements are unique.

This solution ensures we count and process the elements effectively while maintaining an efficient runtime and memory usage.

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?