Number of Good Pairs - Video Solutions

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.