mediumArraysPattern: Divide and Conquer
Count Decaying Pairs Solution
Problem Statement
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
Example 1:
Input:nums = [3, 1, 4, 2]
Output:2
Explanation: The decaying pairs are (0, 1) because 3 - 1 >= 1 - 0, and (2, 3) because 4 - 2 >= 3 - 2. No other pairs satisfy the condition.
Example 2:
Input:nums = [5, 4, 2, 1]
Output:6
Explanation: All 6 unique pairs (i, j) with i < j satisfy the inequality. For instance, (0, 3) satisfies 5 - 1 >= 3 - 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Time: O(n log n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def count_decaying_pairs(nums: list[int]) -> int:
b = [val + i for i, val in enumerate(nums)]
def merge_sort(arr):
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
left, lc = merge_sort(arr[:mid])
right, rc = merge_sort(arr[mid:])
merged, count, i, j = [], lc + rc, 0, 0
while i < len(left) and j < len(right):
if left[i] >= right[j]: count += (len(left) - i); merged.append(right[j]); j += 1
else: merged.append(left[i]); i += 1
return merged + left[i:] + right[j:], count
return merge_sort(b)[1]