Number of Good Pairs — LeetCode 1512 Python Solution

The problem

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

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.

Python solution

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = Counter()
        for x in nums:
            ans += cnt[x]
            cnt[x] += 1
        return ans

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1512. Number of Good Pairs is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems