# Global And Local Inversions Problem

## Description

LeetCode Problem 775.

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

• 0 <= i < j < n
• nums[i] > nums[j] The number of local inversions is the number of indices i where:
• 0 <= i < n - 1
• nums[i] > nums[i + 1]

Return true if the number of global inversions is equal to the number of local inversions.

Example 1:

``````1
2
3
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.
``````

Example 2:

``````1
2
3
Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.
``````

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 0 <= nums[i] < n
• All the integers of nums are unique.
• nums is a permutation of all the numbers in the range [0, n - 1].

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
// The original order should be [0, 1, 2, 3, 4...], the number i should be on the position i.
// We just check the offset of each number, if the absolute value is larger than 1,
// means the number of global inversion must be bigger than local inversion,
// because a local inversion is a global inversion, but a global one may not be local.
bool isIdealPermutation(vector<int>& A) {
for (int i = 0; i < A.size(); ++i) {
if (abs(A[i] - i) > 1) return false;
}
return true;
}
};
``````