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 C solution uses an array as a frequency counter. As each number is processed, its count in the array gets added to the good pair count, then incremented to indicate its increased frequency.