Understand Count the Misaligned Pairs Problem

Problem Name: Count the Misaligned Pairs

Problem Description:

Count the Misaligned Pairs

Difficulty: Medium

Problem Statement

Given a 0-indexed integer array nums, we define a pair of indices (i, j) as a misaligned pair if:

( i < j )
The difference between the indices is not equal to the difference between the corresponding values. In other words, the pair is misaligned if:

j - i ≠ \text{nums}[j] - \text{nums}[i]

Your task is to determine the total number of misaligned (or "bad") pairs in the array.

Examples

Example 1

Input: nums = [3, 3, 3]
Output: 3
Explanation:
- For the pair ((0, 1)): (1-0 ≠ 3 - 3) (i.e. (1 ≠ 0))
- For the pair ((0, 2)): (2 ≠ 3 - 3) (i.e. (2 ≠ 0))
- For the pair ((1, 2)): (1 ≠ 3 - 3) (i.e. (1 ≠ 0))

Thus, there are 3 bad pairs in total.

Example 2

Input: nums = [5, 6, 7, 8]
Output: 0
Explanation: This array forms an arithmetic progression with a common difference of 1. For every valid pair ((i, j)):

j - i = \text{nums}[j] - \text{nums}[i]

Hence, there are no bad pairs.

j - i ≠ \text{nums}[j] - \text{nums}[i]

Therefore, no pairs are misaligned.

Constraints

1 \leq \text{nums.length} \leq 10^5

1 \leq \text{nums[i]} \leq 10^9

Additional Details

The goal is to count the number of pairs that do not follow the natural alignment between the index difference and the value difference. This problem challenges you to design an efficient solution that can handle large input sizes without explicitly checking every possible pair.

Category:No additional categories provided

Programming Language:
Java

Reference Link:

https://leetcode.com/problems/count-number-of-bad-pairs/description

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

Main Function is not defined.

Helper Function:

INPUT: nums = [1, 2, 3, 4, 5]

Output: 0

public long countBadPairs(int[] nums) {

int n = nums.length;

long totalPairs = (long) n * (n - 1) / 2;

Map<Long, Long> freq = new HashMap<>();

for (int i = 0; i < n; i++) {

long key = i - (long) nums[i];

freq.put(key, freq.getOrDefault(key, 0L) + 1);

}//Loop End

long goodPairs = 0;

for (long count : freq.values()) {

goodPairs += count * (count - 1) / 2;