algoadvance

Leetcode 3162. Find the Number of Good Pairs I

Problem Statement:

Given an array of integers nums, a pair (i, j) is called good if nums[i] == nums[j] and i < j. Write a function to return the number of good pairs in the array.

Clarifying Questions:

1. Input Constraints:
   • What is the size range of the array nums?
   • What is the range of values within the nums array? Are they all integer values?
2. Edge Cases:
   • What should be returned if the array is empty?
   • Are all elements in the array unique, or can there be duplicates?
3. Output:
   • The output should be a single integer representing the number of good pairs.

Strategy:

To solve this problem optimally, we can use a hash map (or dictionary) to keep track of the frequency of each number as we iterate through the list.

• As we iterate through the nums array:
  • For each number, count how many times we’ve seen it so far.
  • For each appearance of nums[i], all previous identical values nums[j] (where i > j) form a good pair.

By keeping a frequency map and updating the count of good pairs on the fly, we can efficiently determine the number of good pairs without needing to check every possible pair explicitly.

Time Complexity:

• The time complexity of this solution is O(n) where n is the length of the array nums. This is because we are iterating through the array once and using a hash map to store counts.
• The space complexity is also O(n) in the worst case where all elements are unique and thus stored in the map.

Code:

import java.util.HashMap;

public class Solution {
    public int numIdenticalPairs(int[] nums) {
        // HashMap to store frequency of elements
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        int goodPairs = 0;

        // Iterate through the array
        for (int num : nums) {
            if (freqMap.containsKey(num)) {
                goodPairs += freqMap.get(num);
                freqMap.put(num, freqMap.get(num) + 1);
            } else {
                freqMap.put(num, 1);
            }
        }

        // Return the number of good pairs found
        return goodPairs;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3, 1, 1, 3};
        System.out.println(solution.numIdenticalPairs(nums)); // Output: 4
    }
}

Explanation:

1. Initialization:
   • Create a HashMap named freqMap to store the frequency of each number as we traverse the array.
   • Initialize goodPairs to 0 to keep count of good pairs.
2. Iteration:
   • For each number in the array nums:
     • Check if the number exists in the freqMap.
     • If it does, add the current count of that number (from the map) to goodPairs and increment its count in the map.
     • If it doesn’t, add the number to the map with a count of 1.
3. Output:
   • Once the iteration is complete, return the value of goodPairs.

This approach ensures that we correctly count all 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?