Global and Local Inversions: The Key Insight

LeetCode Global and Local Inversions (problem 775) gives you a permutation of integers from 0 to n-1. A global inversion is any pair (i, j) where i < j and nums[i] > nums[j]. A local inversion is a pair where nums[i] > nums[i + 1], that is, two adjacent elements out of order. You need to return true if the number of global inversions equals the number of local inversions.

The brute-force approach would count both types of inversions separately and compare. But that takes O(n^2) time for global inversions. There is a much cleaner O(n) solution hiding behind one key observation.

Why this problem matters

At first glance this looks like it requires counting inversions, maybe with merge sort or a BIT (binary indexed tree). Those approaches work but they are overkill. The real lesson here is about recognizing when a problem has a simpler structure than it appears.

The critical observation is that every local inversion is automatically a global inversion. If nums[i] > nums[i + 1], then we have i < i + 1 and nums[i] > nums[i + 1], which satisfies the definition of a global inversion. So local inversions are a subset of global inversions.

For the counts to be equal, there must be zero global inversions that are not also local inversions. In other words, the only inversions allowed are adjacent swaps. If any element is "too far" from where it belongs, a non-local global inversion must exist, and the answer is false.

The key insight

Since local inversions are a subset of global inversions, the question becomes: are there any global inversions that are NOT local? A non-local global inversion means nums[i] > nums[j] where j > i + 1. For that to happen, some element must have traveled more than one position from its sorted location.

Think about it. In a permutation of 0 to n-1, element k belongs at index k in the sorted order. If nums[i] = k and abs(k - i) > 1, then that element is at least 2 positions away from where it should be. That displacement guarantees a non-local global inversion exists.

So the entire problem reduces to one check: does every element satisfy abs(nums[i] - i) <= 1?

def is_ideal_permutation(nums):
    for i in range(len(nums)):
        if abs(nums[i] - i) > 1:
            return False
    return True

One pass. No counting. No merge sort. Just check whether every element is within one step of its home position.

Step-by-step walkthrough

In the examples above, you can see the pattern clearly. When an array is already sorted or has only adjacent swaps, the counts match. The moment an element jumps more than one position (like 2 sitting at index 0 in [2, 0, 1]), a non-local global inversion appears and the answer is false.

The definition boxes at the top and bottom of the walkthrough summarize the logic: local inversions are always global, so we only need to verify no extra global inversions exist. Checking abs(nums[i] - i) > 1 catches exactly those cases.

Alternative: track running maximum

There is another clean approach. Instead of checking displacement, you can track the maximum of all elements up to index i - 2. If that maximum exceeds nums[i], you have found a non-local global inversion, because some earlier element (at least 2 positions back) is larger than the current element.

def is_ideal_permutation(nums):
    max_so_far = 0
    for i in range(2, len(nums)):
        max_so_far = max(max_so_far, nums[i - 2])
        if max_so_far > nums[i]:
            return False
    return True

This works because max_so_far holds the largest value from nums[0] through nums[i - 2]. If that value is bigger than nums[i], there is a pair (j, i) where j <= i - 2 and nums[j] > nums[i]. That is a global inversion that is not local.

Both approaches are O(n) time and O(1) space. The displacement check is more intuitive once you understand why it works. The running maximum approach is a nice alternative if the displacement reasoning does not click immediately.

Complexity analysis

Both solutions scan the array exactly once and use constant extra memory. You cannot do better than O(n) since you need to look at every element at least once.

Edge cases to watch for

• Single element or two elements: arrays of length 1 always return true. Arrays of length 2 return true as long as the only possible inversion is local (which it always is for adjacent pairs).
• Already sorted: zero inversions of both types. Return true.
• Reverse sorted (length > 2): for [2, 1, 0], element 2 is at index 0, which is 2 positions away. Return false.
• Only adjacent swaps: [1, 0, 3, 2] has two local inversions and two global inversions. Every element is at most 1 step from its sorted position. Return true.
• Large displacement at the end: do not forget to check the last few elements. A displacement at any index is enough to return false.

The building blocks

Array observation: displacement from sorted position

This problem hinges on comparing each element to its expected position in a sorted array. Since the input is a permutation of 0 to n-1, the sorted position of value k is simply index k. That makes the displacement check trivial: abs(nums[i] - i).

This "compare to sorted position" idea appears in other problems too:

• First Missing Positive uses cyclic sort to place each value at its "home" index, then scans for the first mismatch.
• Find All Numbers Disappeared in an Array uses the same index-as-value mapping to mark which values are present.
• Sort Colors partitions elements to their expected zones based on value.

Whenever a problem gives you a permutation or a range of integers, ask yourself: can I compare each element to where it "should" be? That comparison often unlocks an O(n) solution.

From understanding to recall

The insight behind this problem is satisfying once it clicks. Local inversions are a subset of global inversions, so equality means no extras. The displacement check follows naturally. But knowing the insight and reproducing it under time pressure are different things. Spaced repetition closes that gap. You revisit the problem a few days later, then a week, then a month. Each time the reasoning gets faster until the check abs(nums[i] - i) > 1 is the first thing you write, not the last thing you derive.

Related posts

• Next Permutation
• Majority Element
• Sort Colors