Maximum Number Of Pairs In Array - Leetcode Solution

Problem Statement:

Given an array nums of integers, return the maximum number of pairwise distinct elements pairs that can be formed. Pairs (i, j) and (j, i) are considered distinct.

Example:

Input: nums = [1,3,1,3,2,1,2,2] Output: 4 Explanation: The maximum number of pairs is formed by (1,2),(1,3),(2,3) and (2, 4).

Solution:

Approach 1: Using HashMap

We can use a HashMap to count the frequency of each element in the array. Then we can iterate through the HashMap and calculate the number of pairwise distinct element pairs that can be formed for each element. Finally, we can sum up all the pairwise distinct element pairs to get the maximum number of pairs that can be formed.

Let's see the implementation for the same:

Python Code:

class Solution: def maxNumberOfPairs(self, nums: List[int]) -> int: freq = {} for num in nums: if num in freq: freq[num] += 1 else: freq[num] = 1

    count = 0
    for key in freq:
        if freq[key] >= 2:
            count += (freq[key] * (freq[key] - 1)) // 2
    
    return count

Complexity Analysis:

Time Complexity: O(N), where N is the length of the input array. We need to iterate through the array once to count the frequency of each element and once through the frequency dictionary to calculate the pairwise distinct element pairs. Space Complexity: O(N), as we need to store the frequency of each element in a dictionary.

Approach 2: Using Counting Sort

We can optimize the above approach further by using counting sort. We can create a count array of size max(nums) + 1 and count the frequency of each element in the input array. Then we can calculate the pairwise distinct element pairs for each element using the count array.

Let's see the implementation for the same:

Python Code:

class Solution: def maxNumberOfPairs(self, nums: List[int]) -> int: max_num = max(nums) count = [0] * (max_num + 1) for num in nums: count[num] += 1

    res = 0
    for i in range(max_num + 1):
        res += (count[i] * (count[i] - 1)) // 2
    
    return res

Complexity Analysis:

Time Complexity: O(N + M), where N is the length of the input array and M is the maximum element in the array. We need to iterate through the array once to count the frequency of each element and once through the count array to calculate the pairwise distinct element pairs. Space Complexity: O(M), as we need to create a count array of size M to count the frequency of each element.

1