Number of Good Pairs - Practice Coding Problems

Number of Good Pairs - 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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Good pairs are: (0,3), (0,4), (3,4), (2,5). nums[0]==nums[3]=1, nums[0]==nums[4]=1, nums[3]==nums[4]=1, nums[2]==nums[5]=3.

Example 2 — No Pairs

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

› Output: 0

💡 Note: All elements are unique, so no good pairs exist where nums[i] == nums[j] with i < j.

Example 3 — All Same

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

› Output: 6

💡 Note: All pairs are good: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). With 4 identical elements, we get 4×3/2 = 6 pairs.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,1,1,3] - find identical values at different positions

Process

Compare all pairs where first index < second index

Output

Count of good pairs: 4

Key Takeaway

🎯 Key Insight: Use frequency counting to avoid checking all pairs - for n identical elements, there are n×(n-1)/2 possible pairs

Asked in

LC LeetCode 15 G Google 8

The key insight is that for any number appearing n times, it forms n×(n-1)/2 good pairs. The optimal approach uses a hash map to count pairs as we iterate, achieving O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count - Hash Map	O(n)	O(n)	Count frequency of each element, then calculate pairs using math formula
One Pass Count - Optimized	O(n)	O(n)	Count pairs as we iterate, adding current frequency when we see a number
Brute Force - Nested Loops	O(n²)	O(1)	Check every pair (i,j) where i < j to see if nums[i] == nums[j]

Frequency Count - Hash Map — Algorithm Steps

Count frequency of each number using hash map
For each number with frequency n, add n*(n-1)/2 to result
Return total count of good pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Build frequency map of each number

Calculate

Apply formula n*(n-1)/2 for each frequency

Sum

Add all pair counts together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10001

int solution(int* nums, int numsSize) {
    int freq[MAX_SIZE] = {0};
    int offset = 5000; // Handle negative numbers
    
    // Count frequency of each number
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i] + offset]++;
    }
    
    // Calculate pairs for each number
    int count = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        if (freq[i] > 1) {
            count += freq[i] * (freq[i] - 1) / 2;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to count frequencies, then iterate through unique values

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency of each unique element, worst case all elements are unique

⚡ Linearithmic Space

128.0K Views

Medium Frequency

~10 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count - Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler