# 1512. Number of Good Pairs

# Given an array of integers nums.
# A pair(i, j) is called good if nums[i] == nums[j] and i < j.
# Return the number of good pairs.

# Example 1:
# Input: nums = [1, 2, 3, 1, 1, 3]
# Output: 4
# Explanation: There are 4 good pairs(0, 3), (0, 4), (3, 4), (2, 5) 0-indexed.

# Example 2:
# Input: nums = [1, 1, 1, 1]
# Output: 6
# Explanation: Each pair in the array are good.

# Example 3:
# Input: nums = [1, 2, 3]
# Output: 0

import collections


class Solution1(object):
    def numIdenticalPairs(self, nums):
        dic = collections.defaultdict(list)
        rs = 0

        for i, val in enumerate(nums):
            if len(dic[val]):
                for j in dic[val]:
                    if i > j:
                        rs += 1

            dic[val].append(i)

        return rs


class Solution2(object):
    def numIdenticalPairs(self, nums):
        dic = {}
        for num in nums:
            dic[num] = dic.get(num, 0) + 1

        ans = 0
        for num, freq in dic.items():
            ans += int(freq * (freq-1)/2)

        return ans
