Global and Local Inversions - Video Solutions

Problem Overview: You are given a permutation of numbers from 0 to n-1. A local inversion occurs when nums[i] > nums[i+1], while a global inversion occurs when nums[i] > nums[j] for any i < j. The task is to check whether the total number of global inversions is exactly equal to the number of local inversions.

For the two counts to match, every global inversion must also be a local inversion. That means the array cannot contain any inversion where the distance between indices is greater than one. Any such pair automatically makes global inversions exceed local inversions.

Approach 1: Max Constraint Check (O(n) time, O(1) space)

This approach scans the array while tracking the maximum value seen so far up to index i. For each position, compare that maximum with nums[i+2]. If the previous maximum is greater than nums[i+2], a non-local global inversion exists because the larger element appears at least two indices before a smaller one. That directly violates the condition that all global inversions must be local.

The algorithm performs a single pass through the array and maintains only one running maximum. The moment a violation is detected, you can return false. If no such pair appears, every inversion is adjacent. This method is efficient because it avoids explicitly counting inversions and relies on a simple constraint check derived from the permutation structure. Problems involving permutation properties and constraints like this often appear in array reasoning tasks.

Approach 2: Compare Positions (O(n) time, O(1) space)

This method uses a key property of ideal permutations. If global inversions equal local inversions, each element can be displaced from its sorted position by at most one index. In other words, for every index i, the condition |nums[i] - i| ≤ 1 must hold.

You iterate through the array and compute the absolute difference between the value and its index. If any element is more than one position away from where it belongs in the sorted order, that displacement necessarily creates a non-local global inversion. Because the array is a permutation of 0..n-1, this check works in constant space and linear time. The reasoning relies on simple permutation math, which is common in math and array interview problems.

Recommended for interviews: The Max Constraint Check approach is typically expected in interviews because it demonstrates understanding of how global inversions extend beyond adjacent indices. It directly proves that no element two positions ahead violates the ordering constraint. The position comparison trick is shorter and elegant, but explaining the reasoning behind the displacement rule is essential to show deeper insight.