mediumArraysPattern: Mixed
Reverse Index Pairs Count Solution
Problem Statement
You are given an array of integers `arr` of length `n`. Find the maximum number of pairs that can be formed such that the index of the first element is greater than the index of the second element and the value of the first element is less than the value of the second element.
Examples
Example 1:
Input:[4, 3, 2, 1]
Output:6
Explanation: All possible pairs are (1,0), (2,0), (2,1), (3,0), (3,1), (3,2) with index of first element greater than index of second element.
Constraints
- 1 <= n <= 10^5
- -10^9 <= arr[i] <= 10^9
- n is the number of elements in the array
- All elements in the array are distinct
Time: O(n log n) Space: O(n)
The optimized approach involves using a binary indexed tree or a modified merge sort to count the number of pairs that satisfy the condition. This approach has a time complexity of O(n log n) and is more efficient than the brute force approach. It allows us to count the pairs in a single pass.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split()))
res = 0
for j in range(n):
for k in range(j + 1, n):
if arr[k] < arr[j]:
res += 1
print(res)