775. Global and Local Inversions #

Problem #

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.

Problem Summary #

Array A is a permutation of [0, 1, …, N - 1], where N is the length of array A. A global inversion refers to i,j satisfying 0 <= i < j < N and A[i] > A[j] , while a local inversion refers to i satisfying 0 <= i < N and A[i] > A[i+1] . Return true when the number of global inversions in array A is equal to the number of local inversions.

Solution Approach #

The code for this problem is very simple; the focus is on the reasoning process. The ideal situation where [0, 1, ..., N - 1] has no global inversions should be that i is positioned at A[i-1], A[i], or A[i+1]. For example, if 1 is positioned at A[3], then the only element smaller than 1 is 0, so among A[0], A[1], and A[2] there must be 2 elements greater than 1, which inevitably creates a global inversion. [0, 1, ..., N - 1] is the most ideal case, where every element is in its own position. If each element shifts left or right by 1 position, it can still be guaranteed that only local inversions exist; if it shifts left or right by 2 positions, then a global inversion will definitely occur. Therefore, the conclusion is: the ideal situation where no global inversion occurs should be that i is positioned at A[i-1], A[i], or A[i+1]. The code to check this conclusion is very simple: we only need to determine whether the value of A[i] - i is -1, 0, or 1, that is, whether abs(A[i] - i ) ≤ 1.

Code #

package leetcode

func isIdealPermutation(A []int) bool {
	for i := range A {
		if abs(A[i]-i) > 1 {
			return false
		}
	}
	return true
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}