LeetCode Journal # 1

Documenting my daily LeetCode journey here!

Today’s Problem:

1512. Number of Good Pairs

My First Approach

My initial solution was straightforward: compare every element with every other element and count the pairs where the values are equal and i < j.

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j] && i < j) {
                    count++;
                }
            }
        }

        return count;
    }
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(n²)
Space Complexity: O(1)

Why I wanted to optimize it

This solution checks every possible pair, even though most comparisons don’t contribute to the answer. As the input size grows, the number of comparisons increases quadratically.

I realised that I didn’t actually need to compare the current element with every previous element. I only needed to know how many times I’d already seen the current number.

That led me to use a HashMap to store frequencies. If a number has already appeared k times, then the current occurrence immediately creates k new good pairs.

This reduces the time complexity from O(n²) to O(n) while trading a small amount of extra space O(n).

class Solution {
    public int numIdenticalPairs(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count=0;
        int result=0;
        for (int num :  nums){
            count=map.getOrDefault(num, 0);
            result+=count;
            map.put(num,++count);
        }
       return result; 
    }
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity: O(n)
Space Complexity: O(n)