Two approaches:
Approach 1: Count both with BIT
- Count global inversions using BIT (as you did before)
- Count local inversions with a simple loop
- Compare
Approach 2: Mathematical insight
- Every local inversion is global
- Extra globals exist iff some for
- Check if for any (permutation property)
def isIdealPermutation(A):
# Approach 2: O(n) without BIT
for i, val in enumerate(A):
if abs(val - i) > 1:
return False
return True
Sometimes there's a simpler solution than BIT, but the BIT approach teaches the technique.