Formatted question description: https://leetcode.ca/all/775.html
775. Global and Local Inversions (Medium)
We have some permutation A
of [0, 1, ..., N  1]
, where N
is the length of A
.
The number of (global) inversions is the number of i < j
with 0 <= i < j < N
and A[i] > A[j]
.
The number of local inversions is the number of i
with 0 <= i < N
and A[i] > A[i+1]
.
Return true
if and only if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: A = [1,0,2] Output: true Explanation: There is 1 global inversion, and 1 local inversion.
Example 2:
Input: A = [1,2,0] Output: false Explanation: There are 2 global inversions, and 1 local inversion.
Note:
A
will be a permutation of[0, 1, ..., A.length  1]
.A
will have length in range[1, 5000]
. The time limit for this problem has been reduced.
Solution 1.
A local inversion must be global inversion, but a global inversion might not be local inversion.
If the number of global and local inversions are the same, global inversions must be all local inversions.
Consider the original array without permutation [0, 1, 2, ..., N  1]
, A[i] = i (0 <= i < N)
.
During the permutation, for each i
, we can only swap A[i]
with A[i  1]
, A[i]
or A[i + 1]
. Otherwise, we will get a global inversion that is not a local inversion.
So we can take a look at the distance (namely, absolute difference) between i
(the original A[i]
) and A[i]
(the A[i]
after swap) for each i
. If the distance is greater than 1, it means that we found a nonlocal global inversion and should return false
.
Proof:
 If
A[i] > i + 1
, at least one number that is smaller thanA[i]
got kicked out from the firstA[i]
numbers, and the distance between this smaller number andA[i]
is at least 2, thus it is a nonlocal global inversion.  If
A[i] < i  1
, at least one number that is greater thanA[i]
got kicked out from the lastn  i
numbers, and the distance between this bigger number andA[i]
is at least 2, thus it’s a nonlocal global inversion.
// OJ: https://leetcode.com/problems/globalandlocalinversions/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/globalandlocalinversions/discuss/113656/My3linesC%2B%2BSolution
class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
for (int i = 0; i < A.size(); ++i) {
if (abs(A[i]  i) > 1) return false;
}
return true;
}
};
Java

class Solution { public boolean isIdealPermutation(int[] A) { if (A == null) return false; if (A.length <= 2) return true; int length = A.length; if (A[0] > 1) return false; for (int i = 1; i < length; i++) { int prev = A[i  1], cur = A[i]; if (cur != i && cur != i  1 && cur != i + 1) return false; if (cur == i  1 && prev != i) return false; } return true; } }

// OJ: https://leetcode.com/problems/globalandlocalinversions/ // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/globalandlocalinversions/discuss/113656/My3linesC%2B%2BSolution class Solution { public: bool isIdealPermutation(vector<int>& A) { for (int i = 0; i < A.size(); ++i) { if (abs(A[i]  i) > 1) return false; } return true; } };

class Solution(object): def isIdealPermutation(self, A): """ :type A: List[int] :rtype: bool """ cmax = 0 for i in range(len(A)  2): cmax = max(cmax, A[i]) if cmax > A[i + 2]: return False return True