How do you solve Number of Good Pairs on LeetCode?

Number of Good Pairs (LeetCode #1512) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Counting occurrences can drastically reduce the number of operations needed to find pairs.

What is the brute force solution for Number of Good Pairs?

The brute force approach for Number of Good Pairs is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of indices in the array to see if they form a good pair. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Good Pairs?

Number of Good Pairs uses the following concepts: Array, Hash Table, Math, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Number of Good Pairs?

Always consider edge cases, such as arrays with all unique elements. Explain your thought process clearly; it shows your understanding of the problem. Practice counting problems with different constraints to get comfortable with frequency maps.

What are common mistakes when solving Number of Good Pairs?

Forgetting to check the condition i < j when counting pairs. Not using a frequency map, leading to unnecessary nested loops.

#1512

Number of Good Pairs

Easy

ArrayHash TableMathCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of checking all pairs, we can count how many times each number appears and use combinatorial math to calculate the number of good pairs. This is more efficient as it reduces the number of operations significantly.

⚙️

Algorithm

4 steps

1Step 1: Create a frequency map (dictionary) to count occurrences of each number in the array.
2Step 2: Initialize a counter to 0 for good pairs.
3Step 3: For each unique number in the frequency map, if it appears n times, add n * (n - 1) // 2 to the counter.
4Step 4: Return the counter.

solution.py7 lines

1def numIdenticalPairs(nums):
2    from collections import Counter
3    count = 0
4    freq = Counter(nums)
5    for n in freq.values():
6        count += n * (n - 1) // 2
7    return count

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once to build the frequency map and then once more to calculate pairs. The space complexity is O(n) due to the storage of the frequency map.

1Counting occurrences can drastically reduce the number of operations needed to find pairs.
2Using combinatorial math helps in efficiently calculating the number of pairs from counts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.