Number of Good Pairs

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

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: The good pairs are (0,3), (0,4), (3,4), (2,5).

Example 2:

• Input: nums = [1,1,1,1]
• Output: 6
• Explanation: The good pairs are (0,1), (0,2), (0,3), (1,2), (1,3), (2,3).

    public int numIdenticalPairs1(int[] nums) {
        var count = 0;
        for (int i = 0; i < nums.length; i ++) {
            for (int j = i + 1; j < nums.length; j ++) {
                if (nums[i] == nums[j]) {
                    count ++;
                }
            }
        }
        return count;
    }

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

class Solution {
    public int numIdenticalPairs(int[] nums) {
        var count = 0;
        var map = new HashMap<Integer, Integer>();
        for (int v: nums) {
            map.put(v, map.getOrDefault(v, 0) + 1);
            if (map.get(v) > 1) {
                count += map.get(v) - 1;
            }
        }
        return count;
    }
<br/>
**Complexity Analysis**

- Hash map: The algorithm uses a hash map to store the frequency of each unique number in the array. In the worst case, if all the numbers are unique, the map will contain N entries. Therefore, the space complexity is , where N is the number of unique elements in the array.
- Other variables: The space used by additional variables like pairCount and n is constant, .
- Overall space complexity:  due to the space required by the hash map.