Introduction

In this blog post, we will explore how to solve the LeetCode problem "2364" 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

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i]. Return the total number of bad pairs in nums. Example 1: Input: nums = [4,1,3,3] Output: 5 Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4. The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1. The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1. The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2. The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0. There are a total of 5 bad pairs, so we return 5. Example 2: Input: nums = [1,2,3,4,5] Output: 0 Explanation: There are no bad pairs. Constraints: 1 <= nums.length <= 105 1 <= nums[i] <= 109

Explanation

Here's the breakdown of the solution:

• Transform the Problem: The condition j - i != nums[j] - nums[i] can be rearranged to nums[i] - i != nums[j] - j. Instead of directly checking pairs, we can compute nums[i] - i for each element.
• Count Frequencies: Use a hash map (dictionary in Python) to count the frequency of each nums[i] - i value.

• Calculate Bad Pairs: The total number of pairs is n * (n - 1) / 2. Subtract the number of good pairs (where nums[i] - i == nums[j] - j) from the total number of pairs to get the number of bad pairs.

• Runtime Complexity: O(n), Storage Complexity: O(n)

Code

    def countBadPairs(nums):
    n = len(nums)
    count = 0
    freq = {}

    for i in range(n):
        diff = nums[i] - i
        if diff in freq:
            freq[diff] += 1
        else:
            freq[diff] = 1

    total_pairs = n * (n - 1) // 2
    good_pairs = 0

    for diff in freq:
        good_pairs += freq[diff] * (freq[diff] - 1) // 2

    return total_pairs - good_pairs