Solution 1 - Brute Force

Use two nested loops to check every pair (i, j) where i < j. If nums[i] == nums[j], increment the count. Return the total count of good pairs.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 1512.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def numIdenticalPairs(self, nums: List[int]) -> int:
        """Number of Good Pairs Function"""
        count = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    count += 1
        return count


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # 4
    print(Solution().numIdenticalPairs([1, 1, 1, 1]))          # 6
    print(Solution().numIdenticalPairs([1, 2, 3]))              # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Hash Map (Counting)

As we iterate through the array, maintain a counter (dictionary) tracking how many times each value has appeared so far. For each element x, the current count cnt[x] tells us how many good pairs can be formed with x as the second element. Add that to the answer, then increment the count.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 1512.2 - Solution 2 - Hash Map (Counting) """

#####################################################################################
# Imports
#####################################################################################
from typing import List
from collections import Counter

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def numIdenticalPairs(self, nums: List[int]) -> int:
        """Number of Good Pairs Function"""
        ans = 0
        cnt = Counter()
        for x in nums:
            ans += cnt[x]
            cnt[x] += 1
        return ans


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().numIdenticalPairs([1, 2, 3, 1, 1, 3]))  # 4
    print(Solution().numIdenticalPairs([1, 1, 1, 1]))          # 6
    print(Solution().numIdenticalPairs([1, 2, 3]))              # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

1512 - Number of Good Pairs

Solution 1 - Brute Force

Solution 2 - Hash Map (Counting)