Number of Good Pairs solution and explanation
Google
TCS
9 more videos on this problem
Number of Good Pairs (LeetCode 1512) | Full solution with visuals and examples | Study AlgorithmsNikhil Lohia · 14:13 · 26K views
Number of Good Pairs - Leetcode 1512 - PythonNeetCodeIO · 11:29 · 21K views
Number of Good Pairs | 3 Approaches | META | Leetcode - 1512codestorywithMIK · 15:34 · 8K views
LeetCode 1512 | Number of Good Pairs | Solution Explained (Java + Whiteboard)Xavier Elon · 11:00 · 5K views
Number of Good Pairs leetcode solution (Problem 1512)Engineering Digest · 7:18 · 4K views
Leetcode Solution - 1512 Number of Good PairsJohn Leonardo · 4:48 · 2K views
1512. Number of Good Pairs (Leetcode Easy)Programming Live with Larry · 1:50 · 1K views
Python Leetcode 1512 Number of Good PairNP Learn · 5:40 · 814 views
LeetCode 1512 | Number of Good Pairs | HashMap | JavaSleepy Cracker · 5:12 · 603 views
LeetCode 1512 Number of Good Pairs | Easy | Counting ApproachLeet Logics · 6:02 · 364 views
The problem
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.
def numIdenticalPairs(nums):
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
count += 1
return count
nums = [1, 2, 3, 1, 1, 3]
print(numIdenticalPairs(nums))public class GoodPairs {
public static int numIdenticalPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1, 1, 3};
System.out.println(numIdenticalPairs(nums));
}
}#include <vector>
#include <iostream>
int numIdenticalPairs(std::vector<int>& nums) {
int count = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (nums[i] == nums[j]) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 3, 1, 1, 3};
std::cout << numIdenticalPairs(nums) << std::endl;
return 0;
}function numIdenticalPairs(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) {
count++;
}
}
}
return count;
}
const nums = [1, 2, 3, 1, 1, 3];
console.log(numIdenticalPairs(nums));#include <stdio.h>
int numIdenticalPairs(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 2, 3, 1, 1, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", numIdenticalPairs(nums, numsSize));
return 0;
}using System;
public class GoodPairs {
public static int NumIdenticalPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 1, 1, 3};
Console.WriteLine(NumIdenticalPairs(nums));
}
}The Python solution uses simple nested loops to detect all pairs (i, j) where nums[i] == nums[j] and i < j, incrementing the count for each pair found.
Time Complexity: O(n^2); each element is compared against remaining elements.
Space Complexity: O(1), due to no extra data structure being used.
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.
def numIdenticalPairs(nums):
count = 0
freq = {}
for num in nums:
count += freq.get(num, 0)
freq[num] = freq.get(num, 0) + 1
return count
nums = [1, 2, 3, 1, 1, 3]
print(numIdenticalPairs(nums))import java.util.HashMap;
public class GoodPairs {
public static int numIdenticalPairs(int[] nums) {
int count = 0;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
count += freq.getOrDefault(num, 0);
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1, 1, 3};
System.out.println(numIdenticalPairs(nums));
}
}#include <vector>
#include <unordered_map>
#include <iostream>
int numIdenticalPairs(std::vector<int>& nums) {
int count = 0;
std::unordered_map<int, int> freq;
for (int num : nums) {
count += freq[num];
freq[num]++;
}
return count;
}
int main() {
std::vector<int> nums = {1, 2, 3, 1, 1, 3};
std::cout << numIdenticalPairs(nums) << std::endl;
return 0;
}function numIdenticalPairs(nums) {
let count = 0;
const freq = {};
for (const num of nums) {
if (freq[num]) {
count += freq[num];
freq[num]++;
} else {
freq[num] = 1;
}
}
return count;
}
const nums = [1, 2, 3, 1, 1, 3];
console.log(numIdenticalPairs(nums));#include <stdio.h>
#include <string.h>
#define MAX_NUM 100
int numIdenticalPairs(int* nums, int numsSize) {
int count = 0;
int freq[MAX_NUM + 1] = {0};
for (int i = 0; i < numsSize; i++) {
count += freq[nums[i]];
freq[nums[i]]++;
}
return count;
}
int main() {
int nums[] = {1, 2, 3, 1, 1, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", numIdenticalPairs(nums, numsSize));
return 0;
}using System;
using System.Collections.Generic;
public class GoodPairs {
public static int NumIdenticalPairs(int[] nums) {
int count = 0;
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in nums) {
if (freq.ContainsKey(num)) {
count += freq[num];
freq[num]++;
} else {
freq[num] = 1;
}
}
return count;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 1, 1, 3};
Console.WriteLine(NumIdenticalPairs(nums));
}
}This Python solution makes use of a dictionary to track how many times each number has appeared. For each element, the count of times it has been seen is added to the total number of good pairs before updating the dictionary with its new frequency.
Time Complexity: O(n), due to single pass.
Space Complexity: O(n), for dictionary holding frequencies.
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.
function numIdenticalPairs(nums: number[]): number {
const cnt: number[] = Array(101).fill(0);
let ans = 0;
for (const x of nums) {
ans += cnt[x]++;
}
return ans;
}func numIdenticalPairs(nums []int) (ans int) {
cnt := [101]int{}
for _, x := range nums {
ans += cnt[x]
cnt[x]++
}
return
}impl Solution {
pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut cnt = [0; 101];
for &x in nums.iter() {
ans += cnt[x as usize];
cnt[x as usize] += 1;
}
ans
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function numIdenticalPairs($nums) {
$ans = 0;
$cnt = array_fill(0, 101, 0);
foreach ($nums as $x) {
$ans += $cnt[$x]++;
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2); each element is compared against remaining elements. |
| Optimized Approach Using Hash Map | Time Complexity: O(n), due to single pass. |
| Counting | – |
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 |
Frequently asked questions
Is Number of Good Pairs easy or hard?
Number of Good Pairs is classified as an Easy problem. The brute force solution is straightforward, but recognizing the hash map counting pattern is the key insight that reduces the complexity from O(n²) to O(n).
How to solve Number of Good Pairs in O(n)?
Traverse the array once and maintain a hash map storing how many times each value has appeared. When encountering a value x, add the current frequency of x to the result because each previous occurrence forms a valid pair with the current index. Then increment the stored frequency for x.
What is the best approach for Number of Good Pairs?
The hash map frequency counting approach is the best solution. Iterate through the array while storing how many times each number has appeared. For every new element, add its existing frequency to the answer, which counts all previously formed pairs. This achieves O(n) time complexity and O(n) space complexity.
What data structure is used in Number of Good Pairs?
A hash table (hash map) is the primary data structure used in the optimal solution. It stores the frequency of each number encountered during the array traversal, enabling constant-time lookups to count previously seen values.
What is the time complexity of Number of Good Pairs?
The optimal solution runs in O(n) time using a hash map to track frequencies of numbers seen so far. Each element requires a constant-time lookup and update. The brute force approach checks all pairs and runs in O(n²) time.
Number of Good Pairs Python or Java solution approach?
Both Python and Java implementations follow the same logic: iterate through the array, check the current frequency of the number in a hash map, add that frequency to the result, and update the map. The algorithm runs in O(n) time and requires O(n) space for the frequency map.
Is Number of Good Pairs asked at Google, Amazon, or Meta?
Array and hash table counting problems like Number of Good Pairs commonly appear in coding interviews at large tech companies including Amazon, Google, and Meta. While this specific problem is classified as easy, it tests a fundamental frequency-counting pattern used in many harder interview questions.