Solving Popular Algorithms: Number of Good Pairs

Welcome back to another week of solving algorithms on leet code. Today, we are going to be looking at a quick and easy algorithm that I think is perfect for beginners: Number of Good Pairs.

What our algorithm needs to say to the pairs…

The Problem

The goal of this problem is, given an array of integers, to find the number of “good” pairs contained in the array and return that number.

Now, a pair is good if it meets two basic criteria. First, if the numbers are the same and second, if the index of the first number is smaller than the index of the second. To put in coding terms, if nums[i] === nums[j] and if i < j, then a pair is considered “good”.

For example, let’s we are given this array:

nums = [1,2,3,1,1,3]

In this example, we will have four pairs of numbers that will meet criteria for “good” pairs specified above. Our pairs themselves will be made up of the indices of numbers in the array that meet the criteria and they are (0,3), (0,4), (2,5), and (3,4).

Since we know hopefully understand the goal of this algorithm, I think it’s time to start solving!

The Solution

From the description of this problem, I figured that the easiest way to solve this algorithm would be to use a nested for loop. I should note that while nested for loops should generally be avoided due to their O(n²) runtime, for some problems I find that ultimately they can still be helpful, particularly in a problem like this where we are trying to find pairs inside an array.

So, basically once we have set up our nested for loop, the only thing left to do will be to check to see if our pairs meet the criteria for “good” pairs. We can accomplish this using a simple conditional statement that will check if the two numbers are the same and if the first index is smaller than the second. Then, if a pair is “good”, we can push it into a “results” array. Finally, once our loops have been completed and all the “good” pairs have been found, we can return the length of our results array and ta da, we will have solved our problem!

Before we move onto looking at the actual code of this solution, I want to just reiterate a point that I am constantly making in my blogs and that is how I helpful it is to create a plan before you begin to solve. Even for simple problems like this one, writing out your solution in english or pseudocode before you begin solving will really help you not only solve problems in general, but solve them quickly. It’s one of my best problem solving tips and has helped me solve problems significantly faster than I did when I would just immediately try to jump in writing code.

Anyway, now that I’ve made my point, let’s look at the code for this solution:

var numIdenticalPairs = function(nums) {
    let results = []
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = 1; j < nums.length; j++) {
            if (nums[i] === nums[j] && i < j) {
                let goodPair = []
                goodPair.push(i,j)
                results.push(goodPair)
            }
        }
    }
    
    return results.length
    
};

I honestly think this solution is straightforward, however if you are a beginner I think it’s a great problem to practice! Also, if you are more advanced, I’d recommend seeing if you could find a solution that doesn’t rely on the slow nested for loop.

As always, good luck and happy coding!

Thumbs up for trying this problem on your own!