# 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:

```python
i < j
nums[i] > nums[j]
```

A local inversion is an index `i` such that:

```python
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:

```text
Are there any global inversions that are not local inversions?
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A permutation array `nums` |
| Output | `True` if global inversions equal local inversions |
| Global inversion | Any pair `i < j` with `nums[i] > nums[j]` |
| Local inversion | Adjacent pair `i, i + 1` with `nums[i] > nums[i + 1]` |

Example function shape:

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

## Examples

Example 1:

```python
nums = [1, 0, 2]
```

Output:

```python
True
```

There is one global inversion:

```text
(0, 1), because 1 > 0
```

There is one local inversion:

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

The counts are equal.

Example 2:

```python
nums = [1, 2, 0]
```

Output:

```python
False
```

Global inversions:

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

Local inversions:

```text
(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:

```python
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:

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

A compact way to check this is:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | Only loop variables are used |

## Implementation

```python
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:

```python
for i, value in enumerate(nums):
```

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

So:

```python
abs(value - i)
```

measures how far the value moved from its sorted position.

If the distance is greater than `1`:

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

then the array has a non-local global inversion.

If no value moves too far:

```python
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]`.

```python
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

```python
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:

| Test | Why |
|---|---|
| `[1,0,2]` | One local inversion and one global inversion |
| `[1,2,0]` | Has non-local global inversion |
| Sorted array | No inversions |
| Single element | No inversions |
| `[2,0,1]` | Value `2` moved too far |
| `[0,2,1]` | Only adjacent inversion |