Global and Local Inversions

Global and Local Inversions

What is this problem about?

The Global and Local Inversions coding problem deals with an array A which is a permutation of 0 to n-1. A "global inversion" is any pair (i, j) where i < j and A[i] > A[j]. A "local inversion" is a pair (i, i+1) where A[i] > A[i+1]. You need to return True if the number of global inversions equals the number of local inversions.

Why is this asked in interviews?

Amazon asks this Math and Array interview pattern to test your analytical thinking. Calculating global inversions usually takes $O(N \log N)$ (using Merge Sort), but this problem can be solved in $O(N)$. The core realization is that every local inversion is also a global inversion. Therefore, for the counts to be equal, there must be no global inversions that are not local. It evaluates your ability to spot this logic shortcut.

Algorithmic pattern used

This problem is solved using a Greedy / Math constraint check.

1. For the counts to be equal, we cannot have any inversion where A[i] > A[j] and j - i > 1.
2. This means the maximum element seen up to index i-2 must be smaller than A[i].
3. Iterate through the array, keeping track of the max_val seen up to i-2.
4. If at any point max_val > A[i], a non-local global inversion exists. Return False.
5. An even simpler mathematical trick: since it's a permutation of 0 to n-1, an element A[i] can only be at index i, i-1, or i+1. If abs(A[i] - i) > 1, return False.

Example explanation

A = [1, 0, 2]

• Local inversions: (1, 0). Count = 1.
• Global inversions: (1, 0). Count = 1. Using the trick abs(A[i] - i):
• abs(1 - 0) = 1 <= 1
• abs(0 - 1) = 1 <= 1
• abs(2 - 2) = 0 <= 1 All elements are within 1 step of their sorted position. Result: True.

A = [1, 2, 0]

• abs(A[2] - 2) = abs(0 - 2) = 2 > 1.
• This means 0 is displaced by 2 positions, creating a global inversion (1, 0) that is not local. Result: False.

Common mistakes candidates make

• Calculating Inversions: Actually trying to count all global inversions using Merge Sort or a Fenwick Tree, which is overkill and risks bugs.
• Misunderstanding the subset: Not realizing that the set of local inversions is strictly a subset of global inversions.

Interview preparation tip

When a problem asks if Property A == Property B, and Property B is strictly a subset of Property A, you just need to search for a single instance of Property A that doesn't fit the definition of B.