leetcode 1512. Number of Good Pairs faster than 92.15% of JavaScript online submissions

Posted on

The way I approached the problem was that we are only looking for equivalent pairs. Meaning if our current value is a 1, the only other values we are concerned with is other 1 values. in [ 1,2,3,4,1,2,3,4,1] when looking at value of once, we only care about index 0 and index 4

Rather then loop through the array every time we need a change values, lets loop through the array one time, and put all the equivalent values together. example. lets get [1,1,1] [2,2] [3,3] [4,4]

To get them all together in one pass, use a dictionary to hold values that are the same. I pushed the index values into the array, but that’s actually not needed. Next step will tell us why

Once we have all equivalent values together, such as [1,1,1] we could loop trough the sub array and make combinations. But using math we actually shorten this, not needed to manually make combinations. I figured there must be a mathematical way to do this. This stackoverflow link gave me the correct mathematical formula to proceed.

var numIdenticalPairs = function(nums) {
    let d = {}     //create dictionary
    nums.forEach( (e,index)=> {  //iterate over array
        //if key does not exist, add it
        if(d[e] === undefined){ d[e] = [index]}
        //else push value to key's array
        else { d[e].push(index) }
    })
    let pairs = 0
    Object.keys(d).forEach(key=>{     //get count of pairs
        let n = d[key].length
        pairs += (n * (n-1))/2
    })
    return pairs
};

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s