775. Global and Local Inversions

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

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)
 */