LeetCode 775: Global and Local Inversions

Problem Restatement

We are given an array nums.

The array is a permutation of all integers from 0 to n - 1.

A global inversion is a pair of indices (i, j) such that:

i < j
nums[i] > nums[j]

A local inversion is an index i such that:

nums[i] > nums[i + 1]

Return True if the number of global inversions is equal to the number of local inversions. Otherwise, return False.

Every local inversion is also a global inversion, because adjacent indices are still a valid pair. So the real question is:

Are there any global inversions that are not local inversions?

Input and Output

Example function shape:

def isIdealPermutation(nums: list[int]) -> bool:
    ...

Examples

Example 1:

nums = [1, 0, 2]

Output:

True

There is one global inversion:

(0, 1), because 1 > 0

There is one local inversion:

index 0, because nums[0] > nums[1]

The counts are equal.

Example 2:

nums = [1, 2, 0]

Output:

False

Global inversions:

(0, 2), because 1 > 0
(1, 2), because 2 > 0

Local inversions:

(1, 2), because 2 > 0

There is one non-local global inversion: (0, 2).

So the answer is False.

First Thought: Count Both Types

We could count all global inversions and all local inversions.

Counting local inversions is easy:

for i in range(n - 1):
    if nums[i] > nums[i + 1]:
        local += 1

But counting global inversions directly takes O(n^2) if we check every pair.

Since n can be large, we should avoid explicit inversion counting.

Key Insight

Every local inversion is already a global inversion.

So the counts are equal exactly when there is no global inversion with distance at least 2.

That means we need to reject any pair:

i + 2 <= j
nums[i] > nums[j]

A compact way to check this is:

abs(nums[i] - i) <= 1

for every index i.

Why?

Since nums is a permutation of 0 to n - 1, the sorted position of value nums[i] is exactly nums[i].

If a value moves more than one position away from its sorted index, it creates a non-local global inversion.

So the permutation is valid only when every value is at most one position away from its natural place.

Algorithm

1. Scan every index i.
2. Check whether:

abs(nums[i] - i) > 1

3. If yes, return False.
4. If the scan finishes, return True.

Correctness

Every local inversion is a global inversion. Therefore, the number of global inversions can equal the number of local inversions only if there are no extra global inversions between non-adjacent indices.

If some value nums[i] is more than one position away from index i, then it must have crossed over at least one non-adjacent value. That creates a global inversion that is not local.

So if abs(nums[i] - i) > 1 for any index, the counts cannot be equal, and the algorithm correctly returns False.

If every value is at most one position away from its sorted position, then the only possible inversions are swaps between adjacent values. Every such inversion is local. Therefore, there are no non-local global inversions, and the number of global inversions equals the number of local inversions.

Thus the algorithm returns the correct answer.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def isIdealPermutation(self, nums: list[int]) -> bool:
        for i, value in enumerate(nums):
            if abs(value - i) > 1:
                return False

        return True

Code Explanation

We scan each index and value:

for i, value in enumerate(nums):

The value value belongs at index value in the sorted array.

So:

abs(value - i)

measures how far the value moved from its sorted position.

If the distance is greater than 1:

if abs(value - i) > 1:
    return False

then the array has a non-local global inversion.

If no value moves too far:

return True

then every global inversion is local.

Alternative Prefix-Max Check

Another way is to directly detect non-local global inversions.

For every j >= 2, check whether any earlier value before j - 1 is greater than nums[j].

class Solution:
    def isIdealPermutation(self, nums: list[int]) -> bool:
        max_before = -1

        for j in range(2, len(nums)):
            max_before = max(max_before, nums[j - 2])

            if max_before > nums[j]:
                return False

        return True

This checks for a pair (i, j) where i <= j - 2 and nums[i] > nums[j].

That is exactly a global inversion that is not local.

Testing

def run_tests():
    s = Solution()

    assert s.isIdealPermutation([1, 0, 2]) is True
    assert s.isIdealPermutation([1, 2, 0]) is False
    assert s.isIdealPermutation([0, 1, 2]) is True
    assert s.isIdealPermutation([0]) is True
    assert s.isIdealPermutation([2, 0, 1]) is False
    assert s.isIdealPermutation([0, 2, 1]) is True

    print("all tests passed")

run_tests()

Test meaning: