Sponsored
Sponsored
This approach involves using two nested loops to check all possible pairs of indices in the array. For each pair, we check if it satisfies the condition for being a good pair and count it if it does.
Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs.
Space Complexity: O(1), as we are not using any additional data structures.
1def numIdenticalPairs(nums):
2 count = 0
3 for i in range(len(nums)):
4 for j in range(i + 1, len(nums)):
5 if nums[i] == nums[j]:
6 count += 1
7 return count
8
9nums = [1, 2, 3, 1, 1, 3]
10print(numIdenticalPairs(nums))The Python solution uses simple nested loops to detect all pairs (i, j) where nums[i] == nums[j] and i < j, incrementing the count for each pair found.
This approach optimizes the search for good pairs using a hash map (or dictionary). Instead of checking each pair directly, we track the number of occurrences of each number as we iterate through the array. For each new element, the number of good pairs it can form is equal to the frequency of the element seen so far.
Time Complexity: O(n), since each element is processed once.
Space Complexity: O(1), considering the fixed size of the frequency array which is independent of input size.
1
This Python solution makes use of a dictionary to track how many times each number has appeared. For each element, the count of times it has been seen is added to the total number of good pairs before updating the dictionary with its new frequency.