[leetcode] Global and Local Inversions

problem

code

1st try: check if 0 <= i < i + 1 < j, a[i] > a[j]

class Solution {
    public boolean isIdealPermutation(int[] A) {
        //check if 0 <= i < i + 1 < j, a[i] > a[j]
        for (int i = 0; i < A.length; i++) {
            int temp = A[i];
            for (int j = i + 2; j < A.length; j++) {
                if (temp > A[j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Time: O(N^2)
Space: O(1)

2nd try: O(N) Time

public class Solution {
    public bool IsIdealPermutation(int[] A) {
        int max = -1;
        for (int i = 2; i < A.Length; i++)
        {
            max = Math.Max(max, A[i - 2]);
            if (max > A[i])
                return false;
        }
        return true;
    }
}

Time: O(N)
Space: O(1)

[0, 1, 2, 3, 6, 4, 5, 7] false 6 4 5
[0, 1, 2, 3, 5, 4, 6, 7] true
[1, 2, 3, 4, 5, 6, 7, 0] false
[1, 2, 3, 4, 7, 5, 6, 0] false
[7, 6, 5, 4, 3, 2, 1, 0] false
As you see below, if there are more than 1 swap, it is not ideal P
ex) 4, 5, 6 => 4, 6, 5 => 6, 4, 5