Introduction

In this blog post, we will explore how to solve the LeetCode problem "1512" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: 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 Constraints: 1 <= nums.length <= 100 1 <= nums[i] <= 100

Explanation

Here's the breakdown of the solution:

• Counting Frequency: The core idea is to count the frequency of each number in the array. We use a dictionary (or array since constraints limit the values to 1-100) to store these counts.
• Calculating Combinations: For each number, if its frequency is n, the number of good pairs it forms is n * (n - 1) / 2. We sum this up for all numbers.

• Optimization: Using an array instead of a dictionary, considering the constraints leads to faster access due to direct indexing.

• Runtime Complexity: O(n), where n is the length of the input array.

• Storage Complexity: O(1) - effectively constant because the size of the frequency array is bounded by the constraint 1 <= nums[i] <= 100.

Code

    def numIdenticalPairs(nums: list[int]) -> int:
    """
    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: 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

    Constraints:
    1 <= nums.length <= 100
    1 <= nums[i] <= 100
    """

    counts = [0] * 101  # Initialize counts for numbers 1 to 100
    good_pairs = 0

    for num in nums:
        counts[num] += 1

    for count in counts:
        if count > 1:
            good_pairs += count * (count - 1) // 2

    return good_pairs