Number of Good Pairs — Day 101(Python)

Photo by Gulyás Bianka on Unsplash

After a long hiatus, I decided to start writing again as a new year resolution. I wanted to start with something easy, hence choosing the following problem.

1512. Number of Good Pairs

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

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 (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

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

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

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

This question is very similar to Two Sum. We have solved this problem before. You can find it here.

A brute force method will traverse through the list of numbers and check if the numbers match.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        output = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if(nums[i] == nums[j]):
                    output += 1
        return output

Complexity

Time Complexity

Since we have 2 for-loops here, hence time complexity is O(N²).

Space Complexity

We are not using any extra space, and hence the space complexity will be O(1).

An optimized method will traverse through the list once, but to save time we use a dictionary to store already traversed elements. The keys will be traversed elements and the values will be the number of times we have seen that number.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        output = 0
        dict_number = dict()
        for n in nums:
            if n in dict_number:
                output += dict_number[n]
                dict_number[n] += 1
            else:
                dict_number[n] = 1
        return output

Complexity

Time Complexity

Since we have 1 for-loop here. Hence time complexity is O(N).

Space Complexity

We are not using any extra space and hence the space complexity will be O(N).