Count Decaying Pairs — Problem Statement & Solution Guide
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.
Examples
Input
[3, 1, 4]
Output
1
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.
Input
[1, 2, 3, 4]
Output
0
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 the inequality to nums[i] + i >= nums[j] + j. By creating a new array where B[k] = nums[k] + k, the problem reduces to counting inversions or, more specifically, pairs where B[i] >= B[j], which can be solved using Merge Sort in O(n log n) time.
Brute Force Approach
Iterate through every possible pair (i, j) using nested loops to check if the condition nums[i] - nums[j] >= j - i holds true. This approach checks all n*(n-1)/2 pairs.
Verified Code Solutions
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 countfunction 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
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.