#1512

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Good Pairs

Count all index pairs in an array where elements match and the first index is smaller, using hash-based scanning efficiently.

array hash table math counting

Problem Statement

Given an integer array nums, determine the total number of good pairs present. A pair (i, j) is good if nums[i] equals nums[j] and i is less than j.

Return the count of all such good pairs. For example, given nums = [1,2,3,1,1,3], the pairs (0,3), (0,4), (3,4), and (2,5) are good, totaling 4 good pairs.

Examples

Example 1

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

Output: 4

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

Each pair in the array are good.

Example 3

Input: nums = [1,2,3]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Hash Map Counting

Traverse the array once and store each number's frequency in a hash map. Then for each unique number, calculate pairs with the formula count * (count - 1) // 2 and sum them.

Single-Pass Incremental Counting

Iterate through the array while maintaining a running hash of seen numbers. For each element, add its current count in the hash to a total good pair counter and then increment its count in the hash map.

Mathematical Combination Optimization

Instead of explicitly generating pairs, use the combination formula nC2 for each number's frequency. This leverages the observation that n occurrences produce n * (n - 1) // 2 good pairs directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to a single pass through the array and hash operations. Space complexity is O(k) where k is the number of unique elements in nums, bounded by 100 per constraints.

What Interviewers Usually Probe

Do you recognize a counting or frequency pattern here?
Consider using a hash map to avoid nested loops.
Ask yourself if you can calculate pairs without generating them explicitly.

Common Pitfalls or Variants

Common pitfalls

Double-counting pairs by iterating over all i < j combinations.
Forgetting that i must be less than j, not just matching values.
Using nested loops unnecessarily instead of leveraging hash counts.

Follow-up variants

Count good pairs where i > j instead of i < j, adjusting logic accordingly.
Determine number of good triplets (i < j < k) with equal values using extended frequency counting.
Compute good pairs under a modulo constraint on the values to test handling of hash keys.

FAQ

What defines a good pair in Number of Good Pairs?

A good pair is a pair of indices (i, j) where nums[i] equals nums[j] and i is less than j.

How does the array scanning plus hash lookup pattern apply?

It allows counting occurrences in a single pass and calculating good pairs efficiently using the frequency map.

Can this approach handle the maximum array size efficiently?

Yes, with 1 <= nums.length <= 100, a hash map approach achieves O(n) time and O(k) space without performance issues.

Is there a formula to count pairs without nested loops?

Yes, for a number appearing n times, the number of good pairs is n * (n - 1) // 2.

What mistakes should I avoid for Number of Good Pairs?

Avoid double-counting, ensure i < j, and don't use unnecessary nested loops when hash counting suffices.

terminal

Solution

Solution 1: Counting

Traverse the array, and for each element $x$, count how many elements before it are equal to $x$. This count represents the number of good pairs formed by $x$ and the previous elements. After traversing the entire array, we obtain the answer.

1

2

3

4

5

6

7

8

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

Continue Practicing

#1814 count nice pairs in an array #1994 the number of good subsets #2001 number of pairs of interchangeable rectangles