How do you solve Number of Good Pairs?

Iterate through nums once, maintaining a hash map of frequencies. For each number, add the current frequency count to the answer before incrementing the count. This counts all pairs formed by the current number with its previous occurrences, achieving O(n) time and O(n) space.

Number of Good Pairs

Q: What is the time complexity of Number of Good Pairs?

O(n). The algorithm iterates through the array once, performing O(1) average-time hash map operations per element.

Q: What pattern does Number of Good Pairs use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When counting pairs or combinations of identical elements, track frequencies incrementally and add the current frequency to the result before updating it, enabling O(n) counting of pairs without nested loops.

Easy Hash Maps

Problem

Given an integer array nums, return the number of good pairs where a pair (i, j) is good if nums[i] == nums[j] and i < j.

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100

Example

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

Output: 4

The brute-force approach would check every pair (i, j) with i < j, counting those where nums[i] == nums[j]. This is O(n²) and inefficient for large inputs. The optimal approach uses a frequency map to count how many times each number has appeared so far. For each new occurrence of a number, the number of good pairs increases by the count of previous occurrences of that number. For example, when processing the first '1', no pairs are formed. The second '1' forms one pair with the first. The third '1' forms two pairs with the previous two '1's, adding to the total count. This incremental counting avoids nested loops and achieves O(n) time.

Approach

Straightforward Solution

A brute-force nested loop checks all pairs (i, j) with i < j, comparing nums[i] and nums[j]. This approach is O(n²) and inefficient for larger arrays.

Core Observation

Each good pair corresponds to two identical numbers at different indices with the first index less than the second. Counting pairs directly is equivalent to counting combinations of identical elements.

Path to Optimal

Preview

The key insight is that for each number, the number of new good pairs formed when encountering it again equals the count of how many times it has appeared before…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums once, maintaining a hash map of frequencies. For each number, add the current frequency count to the answer before incrementing the count…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once, performing O(1) average-time hash map operations per element.

Space

O(n)

The hash map stores counts for each unique number, which in the worst case can be all n elements.

Pattern Spotlight

Hash Maps (Frequency Counting)

When counting pairs or combinations of identical elements, track frequencies incrementally and add the current frequency to the result before updating it, enabling O(n) counting of pairs without nested loops.

Solution

Python

1from collections import defaultdict
2
3class Solution:
4    def numIdenticalPairs(self, nums: List[int]) -> int:
5        freq = defaultdict(int)
6        ans = 0
7
8        for n in nums:
9            ans += freq[n]   
10            freq[n] += 1
11
12        return ans     

Step-by-Step Solution

Accumulate Good Pairs by Tracking Frequencies in One Pass

5freq = defaultdict(int)
6ans = 0
8for n in nums:
9    ans += freq[n]   
10    freq[n] += 1
12return ans     

Objective

To count the number of good pairs by incrementally adding the frequency of each number before updating it.

Key Insight

Each time a number is encountered, the number of new good pairs formed equals how many times it has appeared before. By adding the current frequency to the answer before incrementing, the algorithm counts all pairs involving the current element and its previous occurrences without double counting or nested loops.

Interview Quick-Check

Core Logic

Add the current frequency of the number to the answer before incrementing the frequency to count all pairs formed by the current occurrence.

State & Boundaries

Initialize frequencies to zero and increment after counting pairs to maintain correct pair ordering (i < j).

Common Pitfalls & Bugs

Adding the frequency after incrementing would overcount pairs or count pairs with the same index.

Complexity

This approach achieves O(n) time and O(n) space, optimal for this problem.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

ans += freq[n]

Add the current frequency of the number to the answer.

This line counts all new good pairs formed by the current occurrence with all previous occurrences of the same number, ensuring pairs are counted exactly once and respecting the order i < j.

Line 10 Critical

freq[n] += 1

Increment the frequency count for the current number.

Updating the frequency after counting pairs ensures that future occurrences will correctly count pairs with this occurrence.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does adding the current frequency count to the answer before incrementing correctly count all good pairs?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Number of Good Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Number of Good Pairs drill

or drill a free problem

1	`from collections import defaultdict`
2
3	`class Solution:`
4	`def numIdenticalPairs(self, nums: List[int]) -> int:`
5	`freq = defaultdict(int)`
6	`ans = 0`
7
8	`for n in nums:`
9	`ans += freq[n]`
10	`freq[n] += 1`
11
12	`return ans`

5	`freq = defaultdict(int)`
6	`ans = 0`
8	`for n in nums:`
9	`ans += freq[n]`
10	`freq[n] += 1`
12	`return ans`