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.

Description Hints 1 Solution Video 14:13

1512. Number of Good Pairs

Easy89.9% acceptance10 companies

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 <= 100
1 <= nums[i] <= 100

Asked at 10 companies

Sony Htc Zoho Accenture

Google Amazon Microsoft Bloomberg

TCS Meta

Topics

Hints open one at a time

Hint 1

Count how many times each number appears. If a number appears n times, then n * (n – 1) // 2 good pairs can be made with this number.

14:13

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution