Count Decaying Pairs — Problem Statement & Solution Guide

ArraysMediumDivide and Conquer

TimeO(n log n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Array Transformation and Inversion Count (Divide and Conquer / Fenwick Tree)

TopicArrays

PatternDivide and Conquer

TimeO(n log n)

SpaceO(n)

Problem Description

Given an integer array nums of size n, a pair of indices (i, j) is called decaying if it satisfies the following conditions: - 0 <= i < j < n - nums[i] - nums[j] > j - i. Return the total number of decaying pairs in the array.

DSA Pattern Breakdown

"Count Decaying Pairs"

medium

WHY DOES IT MATTER?

Counting inversions is a foundational pattern for any problem that asks for ordered pair relationships after a transformation. Mastery of this pattern enables solving a wide range of "greater‑than" or "less‑than" pair counting tasks that appear in competitive programming, database query optimization, and financial risk calculations.

OPTIMIZATION CHALLENGE

The key insight is to linearize the two‑dimensional inequality into a one‑dimensional comparison by adding the index to the array value. This reduction turns a seemingly complex pairwise condition into a standard inversion count, allowing the use of O(n log n) divide‑and‑conquer or BIT techniques.

REAL-WORLD CONNECTION

In a distributed log system, each entry may carry a timestamp plus a logical offset. Detecting out‑of‑order events (e.g., a later entry with a smaller combined timestamp) is analogous to counting decaying pairs, helping engineers identify clock skew or replay attacks.

When you see a condition mixing values and indices, always try to isolate the index term on one side. If you can express the condition as A[i] > A[j] for a transformed array, you instantly unlock powerful existing algorithms.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(n)

Core Theory — Why This Approach?

The decaying‑pair condition can be algebraically transformed. Starting from nums[i] - nums[j] > j - i, moving terms gives nums[i] + i > nums[j] + j. Defining a new array transformed[i] = nums[i] + i, the problem reduces to counting the number of index pairs (i, j) with i < j and transformed[i] > transformed[j]. This is exactly the classic inversion counting problem. A naive double loop checks every pair in O(n²) time, which quickly exceeds limits for n up to 2·10⁵ or larger. The optimal paradigm leverages divide‑and‑conquer (merge sort) or a Fenwick/BIT tree to count inversions while maintaining O(n log n) time and O(n) auxiliary space. Both approaches maintain a sorted view of the suffix/prefix and accumulate how many previously seen elements are greater than the current one, yielding the total decaying pairs efficiently.

Interview Questions on This Problem

Q1How would you modify the inversion‑counting solution if the condition were nums[i] - nums[j] >= j - i?

Rewrite the inequality to nums[i] + i >= nums[j] + j, which translates to counting pairs where transformed[i] >= transformed[j]. During merge sort, when merging, use a "greater‑or‑equal" comparison and adjust the count accordingly (i.e., count elements in the right half that are less than or equal to the current left element).

Q2Can you solve the decaying‑pair count using a Fenwick Tree? Outline the steps.

First compute transformed[i] = nums[i] + i for all i. Coordinate‑compress these values to a rank range [1..m]. Iterate i from left to right, and for each transformed[i] query the Fenwick tree for the sum of counts of values greater than its rank (i.e., total so far minus prefix sum up to rank). Add this to the answer, then update the tree at its rank by 1. This yields O(n log n) time.

Q3What is the time‑space trade‑off between using merge‑sort based inversion counting versus a BIT for this problem?

Merge sort uses O(n) extra space for the temporary array but no explicit coordinate compression, while BIT requires O(n) space for the tree plus O(n) for compression. Both run in O(n log n) time; BIT may have a smaller constant factor but adds the overhead of compression, whereas merge sort is simpler to implement without extra preprocessing.

Examples

Example 1

Input

[3, 1, 4]

Output

Explanation: Step-by-step: with input [3, 1, 4], we check each pair of indices (i, j) where 0 <= i < j < n. For the pair (0, 1), nums[0] - nums[1] = 3 - 1 = 2 and j - i = 1 - 0 = 1. Since 2 > 1, the pair (0, 1) is a decaying pair. For the pair (1, 2), nums[1] - nums[2] = 1 - 4 = -3 and j - i = 2 - 1 = 1. Since -3 < 1, the pair (1, 2) is not a decaying pair. Therefore, there is only 1 decaying pair.

Example 2

Input

[1, 2, 3, 4]

Output

Explanation: Step-by-step: with input [1, 2, 3, 4], we check each pair of indices (i, j) where 0 <= i < j < n. For the pair (0, 1), nums[0] - nums[1] = 1 - 2 = -1 and j - i = 1 - 0 = 1. Since -1 < 1, the pair (0, 1) is not a decaying pair. For the pair (1, 2), nums[1] - nums[2] = 2 - 3 = -1 and j - i = 2 - 1 = 1. Since -1 < 1, the pair (1, 2) is not a decaying pair. For the pair (2, 3), nums[2] - nums[3] = 3 - 4 = -1 and j - i = 3 - 2 = 1. Since -1 < 1, the pair (2, 3) is not a decaying pair. Therefore, there are 0 decaying pairs.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Transform each element to nums[i] + i, then count inversions in the transformed array using merge sort or a Fenwick tree, achieving O(n log n) time.

Brute Force Approach

Loop over all i < j, check if nums[i] - nums[j] > j - i, and increment a counter. This runs in O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

function countDecayingPairs(nums) {
  const b = nums.map((val, i) => val + i);
  function mergeSort(arr) {
    if (arr.length <= 1) return [arr, 0];
    const mid = Math.floor(arr.length / 2);
    const [left, leftCount] = mergeSort(arr.slice(0, mid));
    const [right, rightCount] = mergeSort(arr.slice(mid));
    let merged = [], count = leftCount + rightCount, i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] > right[j]) {
        count += (left.length - i);
        merged.push(right[j++]);
      } else if (left[i] < right[j]) {
        merged.push(left[i++]);
      } else {
        i++;
        j++;
      }
    }
    return [merged.concat(left.slice(i)).concat(right.slice(j)), count];
  }
  return mergeSort(b)[1];
}

function countDecayingPairs(nums) {
  const b = nums.map((val, i) => val + i);
  function mergeSort(arr) {
    if (arr.length <= 1) return [arr, 0];
    const mid = Math.floor(arr.length / 2);
    const [left, leftCount] = mergeSort(arr.slice(0, mid));
    const [right, rightCount] = mergeSort(arr.slice(mid));
    let merged = [], count = leftCount + rightCount, i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] > right[j]) {
        count += (left.length - i);
        merged.push(right[j++]);
      } else if (left[i] < right[j]) {
        merged.push(left[i++]);
      } else {
        i++;
        j++;
      }
    }
    return [merged.concat(left.slice(i)).concat(right.slice(j)), count];
  }
  return mergeSort(b)[1];
}

#include <vector>
using namespace std;
long long mergeAndCount(vector<long long>& b, int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    long long count = mergeAndCount(b, left, mid) + mergeAndCount(b, mid + 1, right);
    vector<long long> temp; int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (b[i] >= b[j]) { count += (mid - i + 1); temp.push_back(b[j++]); } 
        else temp.push_back(b[i++]);
    }
    while (i <= mid) temp.push_back(b[i++]);
    while (j <= right) temp.push_back(b[j++]);
    for (int k = 0; k < temp.size(); ++k) b[left + k] = temp[k];
    return count;
}
long long countDecayingPairs(vector<int>& nums) {
    vector<long long> b; for(int x : nums) b.push_back((long long)x + (&x - &nums[0]));
    return mergeAndCount(b, 0, b.size() - 1);
}

class Solution {
       public int countDecayingPairs(int[] nums) {
           int count = 0;
           int n = nums.length;
           for (int i = 0; i < n; i++) {
               for (int j = i + 1; j < n; j++) {
                   if (nums[i] - nums[j] > j - i) {
                       count++;
                   }
               }
           }
           return count;
       }
   }

def count_decaying_pairs(nums):
       count = 0
       n = len(nums)
       for i in range(n):
           for j in range(i + 1, n):
               if nums[i] - nums[j] > j - i:
                   count += 1
       return count

function countDecayingPairs(nums) {
  const b = nums.map((val, i) => val + i);
  function mergeSort(arr) {
    if (arr.length <= 1) return [arr, 0];
    const mid = Math.floor(arr.length / 2);
    const [left, leftCount] = mergeSort(arr.slice(0, mid));
    const [right, rightCount] = mergeSort(arr.slice(mid));
    let merged = [], count = leftCount + rightCount, i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] > right[j]) {
        count += (left.length - i);
        merged.push(right[j++]);
      } else if (left[i] < right[j]) {
        merged.push(left[i++]);
      } else {
        i++;
        j++;
      }
    }
    return [merged.concat(left.slice(i)).concat(right.slice(j)), count];
  }
  return mergeSort(b)[1];
}

function countDecayingPairs(nums) {
  const b = nums.map((val, i) => val + i);
  function mergeSort(arr) {
    if (arr.length <= 1) return [arr, 0];
    const mid = Math.floor(arr.length / 2);
    const [left, leftCount] = mergeSort(arr.slice(0, mid));
    const [right, rightCount] = mergeSort(arr.slice(mid));
    let merged = [], count = leftCount + rightCount, i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] > right[j]) {
        count += (left.length - i);
        merged.push(right[j++]);
      } else if (left[i] < right[j]) {
        merged.push(left[i++]);
      } else {
        i++;
        j++;
      }
    }
    return [merged.concat(left.slice(i)).concat(right.slice(j)), count];
  }
  return mergeSort(b)[1];
}

Asked in Top Tech Interviews

Paytm

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.