775.Global-and-Local-Inversions

775. Global and Local Inversions

Solution

• local inversions are all global inversions, but global inversion may not be a local inversion
• if there is a global inversion which is not a local inversion, the result must be false
• as $A[i]\in[0...N-1]$ if $abs(A[i] - 1) > 1$ the final result would be false

class Solution {
  // time complexity O(N) | space complexity O(1)
  public boolean isIdealPermutation(int[] A) {
    int len = A.length;
    for(int i = 0; i < len; i++) {
      if(Math.abs(A[i] - i) > 1)
        return false;
    }

    return true;
  }
}