using System;
using System.Collections.Generic;

public class Solution {
    // time O(n)
    // space O(n)
    public int NumIdenticalPairs(int[] nums) {
        int count = 0;
        Dictionary<int, int> dict = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            if (dict.ContainsKey(nums[i]))
            {
                count += dict[nums[i]];
                dict[nums[i]]++;
            }
            else
            {
                dict[nums[i]] = 1;
            }
        }

        return count;
    }

    // time O(n^2)
    // space O(1)
    // public int NumIdenticalPairs(int[] nums) {
    //     int 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;
    // }

    void Test()
    {
        int[] nums1 = {1,2,3,1,1,3};
        int actual1 = NumIdenticalPairs(nums1);
        if (actual1 != 4)
        {
            throw new Exception("Expected 4, but got " + actual1);
        }

        int[] nums2 = {1,1,1,1};
        int actual2 = NumIdenticalPairs(nums2);
        if (actual2 != 6)
        {
            throw new Exception("Expected 6, but got " + actual2);
        }

        int[] nums3 = {1,2,3};
        int actual3 = NumIdenticalPairs(nums3);
        if (actual3 != 0)
        {
            throw new Exception("Expected 0, but got " + actual3);
        }

        int[] nums4 = {6,5,1,5,7,7,9,1,5,7,1,6,10,9,7,4,1,8,7,1,1,8,6,4,7,4,10,5,3,9,10,1,9,5,5,4,1,7,4,2,9,2,6,6,4,2,10,3,5,3,6,4,7,4,6,4,4,6,3,4,10,1,10,6,10,4,9,6,6,4,8,6,9,5,4};
        int actual4 = NumIdenticalPairs(nums4);
        if (actual4 != 303)
        {
            throw new Exception("Expected 303, but got " + actual4);
        }
    }

    public static void Main(string[] args)
    {
        new Solution().Test();
    }
}