Leetcode 1512. Number of Good Pairs (easy) : NileshBlog.Tech

Leetcode 1512Number of Good Pairs:Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Number of Good Pairs” or “LeetCode .1512‘

Table of Contents

First Approach : bruteforce (Looping) -Number of Good Pairs

The Bruteforce is simplest approach ,we used .The Looping approach contain two loops and it check every possible pair is good pair or not and we count no of good pairs .

The Time complexity of Looping Approach wiill be O(N^2)

Codes: Leet code 1512 Number of Good Pairs

C++: Leet code 1512

#include <vector>

class Solution {
public:
    int numIdenticalPairs(std::vector<int>& nums) {
        int res = 0;

        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] == nums[j]) {
                    res++;
                }
            }
        }
        return res;
    }
};

Java:Leet code 1512

import java.util.List;

public class Solution {
    public int numIdenticalPairs(List<Integer> nums) {
        int res = 0;

        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums.get(i).equals(nums.get(j))) {
                    res++;
                }
            }
        }
        return res;
    }
}

Python:Leet code 1512

from typing import List

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        res = 0

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    res += 1
        return res

JavaScript:Leet code 1512

class Solution {
    numIdenticalPairs(nums) {
        let res = 0;

        for (let i = 0; i < nums.length - 1; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] === nums[j]) {
                    res++;
                }
            }
        }
        return res;
    }
}

Second Approach : Mathimatical Logic – Leetcode 1512 -Number of Good Pairs

Approach is simple as you know in mathmatics to find the permutation and combination we have dedicated formulas and method . same as that we used the combination method to find the no of good pair.

e.g

[1.2.1.1.3.3]

no of(1) = 3 .. 3C1

Calculation : – 3!/2!*1! = 3

no of(2) = 1 …. should be greter than 1 ; = 0

no of(3) = 2 .. 2C1

Calculation : – 2!/2!*0! = 1

Total No of Good pair =3+0+2 =5

The Time complexity of mathmatical Approach wiill be O(N)

Aprroach Algorithm

1: Define the Function

First, we create a function named numIdenticalPairs to solve the problem.

2: Initialize Variables

We start by initializing a variable named count to keep track of the number of identical pairs.
We also create a data structure (an unordered map in C++, a HashMap in Java, a dictionary in Python, and a Map in JavaScript) to store the frequency of each number in the input array.

3: Count Frequencies

We iterate through the input array and use the data structure to count the frequency of each number.

4: Calculate Identical Pairs

After counting the frequencies, we use a mathematical formula to calculate the number of identical pairs for each unique number.
The formula (val * (val - 1)) / 2 calculates the number of pairs for a given frequency val.

5: Accumulate the Results

We accumulate the results for each unique number to get the total number of identical pairs.

6: Return the Result

Finally, we return the count variable, which holds the total number of identical pairs.

Codes : Mathmatical Approach – Leetcode 1512

C++:Leetcode 1512

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

class Solution {
public:
    int numIdenticalPairs(std::vector<int>& nums) {
        int count = 0;
        std::unordered_map<int, int> ans;
        for (int i = 0; i < nums.size(); i++) {
            ans[nums[i]]++;
        }

        for (const auto& it : ans) {
            int val = it.second;
            count = count + (val * (val - 1)) / 2;
        }
        return count;
    }
};

Java: Leetcode 1512

import java.util.HashMap;
import java.util.Map;

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

        for (int val : ans.values()) {
            count = count + (val * (val - 1)) / 2;
        }
        return count;
    }
}

Python: Leetcode 1512

class Solution:
    def numIdenticalPairs(self, nums):
        count = 0
        ans = {}
        for num in nums:
            ans[num] = ans.get(num, 0) + 1

        for val in ans.values():
            count = count + (val * (val - 1)) // 2
        return count

JavaScript: Leetcode 1512

class Solution {
    numIdenticalPairs(nums) {
        let count = 0;
        let ans = new Map();
        for (let num of nums) {
            ans.set(num, (ans.get(num) || 0) + 1);
        }

        for (let val of ans.values()) {
            count = count + (val * (val - 1)) / 2;
        }
        return count;
    }
}

Leetcode 1512. Number of Good Pairs (easy)