Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Number of Good Pairs

Problem Statement

Given an array of integers nums, return the number of good pairs in it.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs, here are the indices: (0,3), (0,4), (3,4), (2,5).

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array is a 'good pair'.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: No number is repeating.

Constraints:

  • 1 <= nums.length <= 100

.....

.....

.....

Like the course? Get enrolled and start learning!
John Daugherty

John Daugherty

· 3 years ago

and the examples don't really help. this could be explained a lot better.

Show 5 replies
A

amazonintern101

· 3 years ago

class Solution:
  def numGoodPairs(self, nums):
    pairCount = 0
    # TODO: Write your code here
    left, right = 0,0
    while left < len(nums) - 1:
      right += 1
      if nums[left] == nums[right] and left < right:
        pairCount += 1

      if right == len(nums) - 1:
        left += 1
        right = left

    return pairCount
Show 2 replies
L

Lukas Marquardt

· 2 years ago

I realized there was a way to solve this in a single line (excluding the import) by using the triangular number formula. There's no real advantage here, except that we don't need to count the pairs separately:

Instead, we count the occurrences n for each number and calculate the number of pairs from 0…n-1

from collections import Counter


class Solution:
  def numGoodPairs(self, nums):
    return sum((v * (v - 1) // 2) for _, v in Counter(nums).items())
J

Jay

· 2 years ago

class Solution {
  numGoodPairs(nums) {
    let pairCount = 0;
    for(let i = 0; i < nums.length; i++) {
      for(let j = i + 1; j < nums.length; j++) {
        if (nums[i] == nums[j]) pairCount++;
      }
    }
    return pairCount;
  }
}
Show 1 reply
Giovanni Aparecido da Silva Oliveira

Giovanni Aparecido da Silva Oliveira

· 2 years ago

Two pointers do it

Trebilcode

Trebilcode

· 3 months ago

class Solution {
  numGoodPairs(nums) {
    let pairCount = 0;
    let i = 0;
    let j = 1;

    while (i < nums.length){
      while(j < nums.length){
        if(nums[i] === nums[j]){ 
          pairCount++;
        }
        j++
      }
      i++;
      j = i + 1;
    }
    return pairCount;
  }
}