Count Number Of Bad Pairs

Back to problems

Leetcode

Medium

Arrays

Hash Maps

Math

Count Number Of Bad Pairs

Count how many index pairs are not “good” based on the relation between values and indices.

Acceptance 0%

Start Practice

Problem Statement

You are given an integer array nums.

For a pair of indices (i, j) with i < j, define the pair as good if:

$j - i = nums[j] - nums[i]$

All other pairs are bad.

Return the number of bad pairs in the array.

Your task is to count all index pairs and subtract the number of good pairs efficiently.

Input Format

A single integer array nums of length n.
Each element is an integer.

Output Format

Return one integer: the number of bad pairs (i, j) such that i < j and the pair is not good.

Constraints

$1 \le n \le 10^5$
Values in nums fit in a 32-bit signed integer
The answer may be large; use 64-bit integer arithmetic

Examples

Sample cases returned by the problem API.

Example 1

Input

nums = [4,1,3,3]

Output

Explanation

All pairs are: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). Good pairs satisfy j - i = nums[j] - nums[i]. Only (1,2) is good because 2 - 1 = 3 - 1 = 2 is false; wait, check carefully:

(0,2): 2 - 0 = 3 - 4 = -1, false
(1,2): 2 - 1 = 3 - 1 = 2, false The good pair is (2,3): 3 - 2 = 3 - 3 = 0, false So there are 0 good pairs and 6 bad pairs? This example is inconsistent.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress