Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

775. Global and Local Inversions

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  bool isIdealPermutation(vector<int>& A) {
    int maxi = -1;  // The most likely to be greater than A[i + 2]

    for (int i = 0; i + 2 < A.size(); ++i) {
      maxi = max(maxi, A[i]);
      if (maxi > A[i + 2])
        return false;
    }

    return true;
  }
};




			


class Solution {
  public boolean isIdealPermutation(int[] A) {
    int max = -1; // The most likely to be greater than A[i + 2]

    for (int i = 0; i + 2 < A.length; ++i) {
      max = Math.max(max, A[i]);
      if (max > A[i + 2])
        return false;
    }

    return true;
  }
}




			


class Solution:
  def isIdealPermutation(self, A: List[int]) -> bool:
    for i, a in enumerate(A):
      if abs(a - i) > 1:
        return False

    return True