LeetCode Problem 1512

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Counting

Solution

LeetCode 1512 - Number of Good Pairs

Problem Understanding

The problem gives us an integer array nums and asks us to count how many pairs of indices (i, j) satisfy two conditions:

1. nums[i] == nums[j]
2. i < j

Such pairs are called "good pairs".

In simpler terms, we need to count how many times the same value appears more than once, and determine how many unique index pairs can be formed from those repeated occurrences.

For example, if a number appears three times, then it forms the following pairs:

• first with second
• first with third
• second with third

That produces 3 good pairs.

The input array length is at most 100, and each value is also between 1 and 100. These constraints are very small, which means even a brute-force solution would work within time limits. However, the problem is designed to test understanding of counting frequencies efficiently using a hash map.

An important detail is that pairs are based on indices, not values alone. Even if two values are identical, they only count if their positions are different and ordered such that i < j.

Several edge cases are important to consider upfront. An array with all unique values should return 0 because no equal pairs exist. An array where all values are identical produces the maximum number of good pairs. Arrays of length 1 also produce 0 because a pair requires two distinct indices. The problem guarantees valid input sizes, so we do not need to handle empty arrays.

Approaches

Brute-Force Approach

The most direct solution is to examine every possible pair of indices (i, j) where i < j.

For each pair, we compare nums[i] and nums[j]. If they are equal, we increment the answer.

This works because every possible pair is checked exactly once, guaranteeing correctness.

However, this approach requires nested loops. If the array length is n, then the total number of comparisons is approximately:

$$\frac{n(n-1)}{2}$$

This leads to O(n²) time complexity.

Although the constraints are small enough that this would pass, we can do better using frequency counting.

Optimal Approach, Hash Map Frequency Counting

The key observation is that when we encounter a number again, every previous occurrence of that same number forms a new good pair with the current index.

Suppose we process the array from left to right.

If we have already seen the number 1 three times, then the next 1 forms exactly three new good pairs, one with each earlier occurrence.

This means we do not need to compare against every earlier element individually. Instead, we only need to know how many times each number has appeared so far.

A hash map is perfect for this because it allows constant-time frequency lookup and update.

As we iterate through the array:

• Look up how many times the current number has appeared
• Add that count to the answer
• Increment the stored frequency

This converts the solution from quadratic time to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible pair explicitly
Optimal	O(n)	O(n)	Uses frequency counting with a hash map

Algorithm Walkthrough

1. Initialize a variable good_pairs to 0.

This variable stores the total number of valid pairs found so far. 2. Create an empty hash map called frequency.

The hash map stores how many times each number has already appeared while traversing the array. 3. Iterate through each number in nums.

We process the array from left to right so that every previously seen occurrence automatically satisfies i < j. 4. For the current number, check how many times it has appeared before.

If the number has already appeared k times, then the current occurrence forms exactly k new good pairs. 5. Add this count to good_pairs.

This accumulates all valid pairs incrementally. 6. Increment the frequency of the current number in the hash map.

This prepares the map for future elements. 7. After processing the entire array, return good_pairs.

Why it works

The algorithm maintains the invariant that the frequency map always contains counts of elements seen before the current index.

When processing an element at index j, every earlier occurrence of the same value corresponds to exactly one valid pair (i, j) where i < j.

Since the algorithm adds the number of previous occurrences directly to the answer, every valid pair is counted exactly once, and no invalid pair is counted.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        frequency = defaultdict(int)
        good_pairs = 0

        for num in nums:
            good_pairs += frequency[num]
            frequency[num] += 1

        return good_pairs

The implementation begins by creating a hash map called frequency. A defaultdict(int) is used so missing keys automatically start with value 0.

The variable good_pairs stores the running total of valid pairs.

As the algorithm iterates through each number, it first adds the current frequency of that number to the answer. This works because every earlier occurrence forms a new pair with the current index.

After counting those pairs, the frequency of the number is incremented so future elements can pair with it.

The final answer is returned after the traversal completes.

Go Solution

func numIdenticalPairs(nums []int) int {
    frequency := make(map[int]int)
    goodPairs := 0

    for _, num := range nums {
        goodPairs += frequency[num]
        frequency[num]++
    }

    return goodPairs
}

The Go implementation follows the exact same logic as the Python version.

Go maps return the zero value for missing keys automatically, so no special initialization is needed before reading frequency[num].

Since the constraints are small, integer overflow is not a concern. Standard int values are sufficient.

Worked Examples

Example 1

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

We process the array from left to right.

Step	Current Number	Previous Frequency	New Pairs Added	Total Pairs	Frequency Map After Update
1	1	0	0	0	{1:1}
2	2	0	0	0	{1:1, 2:1}
3	3	0	0	0	{1:1, 2:1, 3:1}
4	1	1	1	1	{1:2, 2:1, 3:1}
5	1	2	2	3	{1:3, 2:1, 3:1}
6	3	1	1	4	{1:3, 2:1, 3:2}

Final answer:

4

Example 2

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

Step	Current Number	Previous Frequency	New Pairs Added	Total Pairs
1	1	0	0	0
2	1	1	1	1
3	1	2	2	3
4	1	3	3	6

Final answer:

6

The pairs are:

• (0,1)
• (0,2)
• (0,3)
• (1,2)
• (1,3)
• (2,3)

Example 3

Input: nums = [1,2,3]

Step	Current Number	Previous Frequency	New Pairs Added	Total Pairs
1	1	0	0	0
2	2	0	0	0
3	3	0	0	0

Final answer:

0

No value appears more than once.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	The hash map may store up to n distinct values

The algorithm performs one pass through the array. Each hash map lookup and update operation takes average constant time, giving an overall linear runtime.

The extra space depends on how many unique numbers exist in the array. In the worst case, every element is distinct, so the hash map stores n entries.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        frequency = defaultdict(int)
        good_pairs = 0

        for num in nums:
            good_pairs += frequency[num]
            frequency[num] += 1

        return good_pairs

solver = Solution()

assert solver.numIdenticalPairs([1,2,3,1,1,3]) == 4  # example case
assert solver.numIdenticalPairs([1,1,1,1]) == 6      # all identical
assert solver.numIdenticalPairs([1,2,3]) == 0        # no duplicates
assert solver.numIdenticalPairs([5]) == 0            # single element
assert solver.numIdenticalPairs([2,2]) == 1          # smallest valid pair
assert solver.numIdenticalPairs([1,2,1,2,1]) == 4   # multiple repeated groups
assert solver.numIdenticalPairs([100]*100) == 4950   # maximum constraints
assert solver.numIdenticalPairs([1,2,3,4,5,6]) == 0 # strictly unique

Test	Why
[1,2,3,1,1,3]	Validates mixed duplicates
[1,1,1,1]	Validates maximum pair generation
[1,2,3]	Ensures no false positives
[5]	Tests smallest array size
[2,2]	Tests minimal valid pair
[1,2,1,2,1]	Tests multiple duplicate groups
[100] * 100	Stress test at maximum constraint size
[1,2,3,4,5,6]	Tests all unique elements

Edge Cases

One important edge case is an array containing only unique elements. In this situation, every frequency lookup returns zero, so no pairs are added to the answer. The implementation handles this naturally because the hash map starts empty and only increments counts after processing each element.

Another important case is when all elements are identical. This produces the largest possible number of good pairs. For example, four identical numbers produce six pairs. The algorithm handles this correctly because each new occurrence adds all prior occurrences to the answer.

A third edge case is an array with only one element. Since a pair requires two distinct indices, the answer must be zero. The implementation correctly returns zero because the loop executes once, the frequency before insertion is zero, and no pair is added.