775

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.

Related Topics:
Array, Math

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 non-local global inversion and should return false.

Proof:

• If A[i] > i + 1, at least one number that is smaller than A[i] got kicked out from the first A[i] numbers, and the distance between this smaller number and A[i] is at least 2, thus it is a non-local global inversion.
• If A[i] < i - 1, at least one number that is greater than A[i] got kicked out from the last n - i numbers, and the distance between this bigger number and A[i] is at least 2, thus it's a non-local global inversion.

// OJ: https://leetcode.com/problems/global-and-local-inversions/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/global-and-local-inversions/discuss/113656/My-3-lines-C%2B%2B-Solution
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;
    }
};