algoadvance

Leetcode 3162. Find the Number of Good Pairs I

Problem Statement

Given an array of integers, count the number of pairs (i, j) such that 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): nums[0] == nums[3] -> 1 == 1
- (0,4): nums[0] == nums[4] -> 1 == 1
- (3,4): nums[3] == nums[4] -> 1 == 1
- (2,5): nums[2] == nums[5] -> 3 == 3

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair (i,j) with i < j is a good pair.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Clarifying Questions

1. Q: Can we assume the array always has at least one element? A: Yes, based on the constraint 1 <= nums.length.

2. Q: Can the elements be negative or only positive integers? A: Based on the constraint 1 <= nums[i], all elements are positive integers.

3. Q: Should the pairs (i, j) be counted only once even if multiple valid pairs exist? A: Yes, each pair should be counted once as long as i < j and nums[i] == nums[j].

Strategy

1. Brute Force Approach:
   • Iterate through each pair (i, j) in a nested loop where i < j.
   • Check if nums[i] == nums[j].
   • Keep a counter for the good pairs found.
2. Optimal Approach:
   • Use a hash map to keep track of the frequency of each number as we iterate through the array.
   • For each number, if it has been seen before, increment the count of good pairs by its current frequency.
   • Update the frequency of the current number.

This optimal approach reduces the need for the nested loop and provides a more efficient solution.

Time Complexity

• Brute Force Approach: O(n^2), where n is the length of the array. This is due to the nested iteration through all pairs.
• Optimal Approach: O(n), since we only iterate through the array once and perform constant-time operations for each element using a hash map.

Code

Here is the C++ code implementing the optimal approach:

#include <iostream>
#include <vector>
#include <unordered_map>

int numIdenticalPairs(std::vector<int>& nums) {
    std::unordered_map<int, int> countMap;
    int goodPairs = 0;
    
    for (int num : nums) {
        // If num has been encountered before, number of good pairs
        // increases by the count of num seen so far
        if (countMap.find(num) != countMap.end()){
            goodPairs += countMap[num];
        }
        // Increment the frequency of num
        countMap[num]++;
    }
    
    return goodPairs;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 1, 1, 3};
    std::cout << "Number of good pairs: " << numIdenticalPairs(nums) << std::endl;
    return 0;
}

This code uses the optimal approach with a hash map, traversing the array only once to count the good pairs efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?