Count Number of Bad Pairs - Solution & Explanation

This approach involves checking every possible pair of indices (i, j) where i < j and seeing if they satisfy the condition j - i != nums[j] - nums[i]. This will involve nested loops and checking the condition directly.

The C solution uses two nested loops to iterate through all pairs of indices. The outer loop iterates through each element, and the inner loop checks for every element succeeding it. If the condition for a bad pair is satisfied, we increment the counter. The solution is straightforward but not optimal for large inputs due to its O(n^2) complexity.

To improve upon the brute force method, this approach introduces the concept of a hash map (or dictionary) to track the counts of differences calculated by "nums[i] - i". Using this, we can efficiently compute the number of good pairs and then derive the number of bad pairs from it.

The C implementation uses an array to simulate the hash map functionality, storing differences and their occurrences. Each difference is used to quickly calculate how many good & bad pairs exist as the input is processed. This efficient algorithm reduces time complexity to nearly O(n) via its single pass nature.