> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/math/775.-global-and-local-inversions.md).

# 775. Global and Local Inversions

```
T: O(n)
S: O(1)
```

```java
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        for (int i = n - 3; i >= 0; i--) {
            min = Math.min(min, nums[i+2]); // store the most min value
            if (nums[i] > min) { // once there is any past i+2, i+3 .... is smaller -> return false;
                return false;
            }
        }
        return true;
    }
}

/***
global:
0 <= i < j < n
nums[i] > nums[j]


local:
0 <= i < n - 1
nums[i] > nums[i + 1]

so local is part of global
if we can find nums[i] > nums[i + 2,  or i +3 , i+4]
means we have more global -> so return false

how to avoid comparing i+2, i+3, i+4... for each i?
->. record most min value in [i+2, i+3, i+4...] 

T: O(n)
S: O(1)
 */
```