algoadvance

Leetcode 1512. Number of Good Pairs

Problem Statement

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:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5).

Clarifying Questions

  1. What is the size range of the array?
    • The array size can range from 1 to 100.
  2. What is the range of the integers in the array?
    • The integers can range from 1 to 100.
  3. Is it guaranteed that the given array will have integers only?
    • Yes, the array will consist of integers only.

Strategy

  1. Brute Force Approach:
    • Iterate through the array with two loops to check each pair (i, j) where i < j and count the number of good pairs.
    • This approach has a time complexity of O(n^2), which is feasible given the constraints.
  2. Optimized Approach:
    • Use a hashmap to keep track of the counts of each number as we iterate through the array.
    • For each number, if it has been seen before, the number of good pairs involving this number is simply the count of its previous occurrences.
    • This approach has a time complexity of O(n), which is more efficient.

Time Complexity

Code

Here is the C++ solution for the optimized 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(countMap.find(num) != countMap.end()) {
            goodPairs += countMap[num]; // Increase by the count of previous occurrences of `num`
        }
        // Update the count of the current number
        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;
}

Explanation

  1. Initialization:
    • We use an unordered_map countMap to store the count of each number.
    • We initialize goodPairs to 0.
  2. Iteration:
    • For each number in the array nums, we check if it is already in the map.
    • If it is, we add the count of this number (i.e., all previous occurrences) to goodPairs.
    • We then increment the count of this number in the map.
  3. Output:
    • Finally, we return the total count of good pairs.

This approach ensures that we efficiently count the good pairs with a single pass through the array, achieving O(n) time complexity.

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