Solution: Number of Good Pairs

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Number of Good Pairs

Table of Contents

Contents are not accessible

Problem Statement

Given an array of integers nums, return the number of good pairs in it.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs, here are the indices: (0,3), (0,4), (3,4), (2,5).

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array is a 'good pair'.

Example 3:

Input: words = nums = [1,2,3]
Output: 0
Explanation: No number is repeating.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution

We can use a HashMap to store the frequency of each number in the input array nums.

While iterating through the input array, for each number n in the array, we will increment the count of n in the HashMap.

Whenever we find a new occurrence of a number, we have found a new pair.

Every new occurrence of a number can be paired with every previous occurrence of the same number. This means if a number has already appeared p times, we will have p-1 new pairs.

Hence, whenever we find a new occurrence of a number (that is, its count is more than 1), we will add p-1 to pairCount, which keeps track of the total number of good pairs.

Code

Here is the code for this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Loop through the array: The algorithm iterates through the array nums exactly once. For each element, the algorithm performs constant-time operations, such as inserting into the hash map or updating the count of pairs. This results in $O(N)$ time complexity for the loop, where N is the number of elements in the array.
Hash map operations: The operations map.getOrDefault() and map.put() both have an average time complexity of $O(1)$ because hash map operations are generally constant time in average cases.

Overall time complexity: $O(N)$ , where N is the number of elements in the nums array.

Space Complexity

Hash map: The algorithm uses a hash map to store the frequency of each unique number in the array. In the worst case, if all the numbers are unique, the map will contain N entries. Therefore, the space complexity is $O(N)$ , where N is the number of unique elements in the array.
Other variables: The space used by additional variables like pairCount and n is constant, $O(1)$ .

Overall space complexity: $O(N)$ due to the space required by the hash map.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible