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:

1. ( i < j )
2. 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.