Number of Good Pairs - Solution & Explanation
Problem Statement
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 1:
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.
Example 2:
Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3] Output: 0
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approach Overview
Problem Overview: Given an integer array nums, count the number of pairs (i, j) such that nums[i] == nums[j] and i < j. A pair is considered "good" when both indices point to the same value and the first index appears before the second.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The most direct solution checks every possible pair of indices. Use two nested loops: the outer loop selects index i, and the inner loop scans indices j from i + 1 to the end of the array. Each time nums[i] == nums[j], increment the counter. This method performs roughly n * (n-1) / 2 comparisons, which leads to O(n²) time complexity and constant O(1) extra space.
This approach works well for small arrays and helps demonstrate a clear understanding of the problem definition. However, performance degrades quickly as the array grows because every pair is explicitly checked. Problems involving pair counting in an array often require a more efficient counting strategy.
Approach 2: Hash Map Frequency Counting (O(n) time, O(n) space)
A faster solution counts how many times each number has already appeared while iterating through the array. Maintain a hash map where the key is the number and the value is its frequency so far. When processing a new element x, the number of new good pairs formed equals the current frequency of x. Add that frequency to the result, then increment the stored count.
Example: if the value 3 has already appeared 4 times, the next 3 forms 4 new good pairs. This works because each previous occurrence creates one valid pair with the current index. Each iteration performs a constant-time hash lookup and update, producing O(n) time complexity and O(n) space complexity.
This technique relies on frequency tracking, a common pattern in hash table problems and counting problems. Mathematically, the process mirrors the combination formula for choosing two identical values from a group, which connects to counting techniques.
Recommended for interviews: Interviewers typically expect the hash map frequency approach. The brute force method shows you understand the definition of a good pair and can reason about pair enumeration. The optimized solution demonstrates familiarity with hash-based counting patterns and reduces the runtime from quadratic O(n²) to linear O(n), which is the standard expectation for this problem.
Approach 1: Brute Force Approach
This approach involves using two nested loops to check all possible pairs of indices in the array. For each pair, we check if it satisfies the condition for being a good pair and count it if it does.
This C solution uses two for loops to iterate through all pairs of indices. We start with index i and compare it with all subsequent indices j. If a good pair is found, we increment the count variable.
Complexity
Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs.
Space Complexity: O(1), as we are not using any additional data structures.
Approach 2: Optimized Approach Using Hash Map
This approach optimizes the search for good pairs using a hash map (or dictionary). Instead of checking each pair directly, we track the number of occurrences of each number as we iterate through the array. For each new element, the number of good pairs it can form is equal to the frequency of the element seen so far.
This C solution uses an array as a frequency counter. As each number is processed, its count in the array gets added to the good pair count, then incremented to indicate its increased frequency.
Complexity
Time Complexity: O(n), since each element is processed once.
Space Complexity: O(1), considering the fixed size of the frequency array which is independent of input size.
Approach 3: 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.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the array, and C is the range of values in the array. In this problem, C = 101.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), where n is the length of the array. We are checking all possible pairs. |
| Optimized Approach Using Hash Map | Time Complexity: O(n), since each element is processed once. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small input sizes or when demonstrating the basic logic of pair enumeration |
| Hash Map Frequency Counting | O(n) | O(n) | General case and interview settings where linear time is expected |
Video Solution
Number of Good Pairs (LeetCode 1512) | Full solution with visuals and examples | Study Algorithms • Nikhil Lohia • 26,328 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Good Pairs easy or hard?
How to solve Number of Good Pairs in O(n)?
What is the best approach for Number of Good Pairs?
What data structure is used in Number of Good Pairs?
What is the time complexity of Number of Good Pairs?
Number of Good Pairs Python or Java solution approach?
Is Number of Good Pairs asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Number of Good Pairs with our built-in code editor and test cases.
Practice on FleetCode