Global and Local Inversions

medium arrays math

Problem

A permutation has equal global and local inversions iff every value differs from its index by at most 1. Determine whether this holds.

InputA=[1,0,2]

Outputtrue

The only inversion is local: A[0]=1 > A[1]=0.

input

def isIdealPermutation(A):
    for i, v in enumerate(A):
        if abs(v - i) > 1:
            return False
    return True

function isIdealPermutation(A) {
  for (let i = 0; i < A.length; i++)
    if (Math.abs(A[i] - i) > 1) return false;
  return true;
}

boolean isIdealPermutation(int[] A) {
    for (int i = 0; i < A.length; i++)
        if (Math.abs(A[i] - i) > 1) return false;
    return true;
}

bool isIdealPermutation(vector<int>& A) {
    for (int i = 0; i < (int)A.size(); i++)
        if (abs(A[i] - i) > 1) return false;
    return true;
}

Explanation

A local inversion is an adjacent out-of-order pair (A[i] > A[i+1]), and a global inversion is any out-of-order pair A[i] > A[j] with i < j. Since every local inversion is also a global one, the counts are equal exactly when there are no non-local global inversions.

That condition has a beautifully simple test: the array (a permutation of 0..n-1) qualifies if and only if every value sits within distance 1 of its index, i.e. |A[i] - i| <= 1 for all i.

Intuitively, if some value were ever displaced by 2 or more from its sorted position, you could find a far-apart pair that is out of order but not adjacent — a global inversion that isn't local. So the loop just checks each position and returns False the instant it sees abs(v - i) > 1.

Example: A = [1, 0, 2]. At i=0, |1-0| = 1 (ok); at i=1, |0-1| = 1 (ok); at i=2, |2-2| = 0 (ok). Every displacement is within 1, so the answer is true.

This needs just one scan and no extra memory, which is why it is far faster than literally counting inversions.

Time: O(n) Space: O(1)