Algorithm
Problem Name: 775. Global and Local Inversions
Problem Link: https://leetcode.com/problems/global-and-local-inversions/
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 < nnums[i] > nums[j]
The number of local inversions is the number of indices i where:
0 <= i < n - 1nums[i] > nums[i + 1]
Return true if the number of global inversions is equal to the number of local inversions.
Example 1:
Input: nums = [1,0,2] Output: true Explanation: There is 1 global inversion and 1 local inversion.
Example 2:
Input: nums = [1,2,0] Output: false Explanation: There are 2 global inversions and 1 local inversion.
Constraints:
n == nums.length1 <= n <= 1050 <= nums[i] < n- All the integers of
numsare unique. numsis a permutation of all the numbers in the range[0, n - 1].
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const isIdealPermutation = function(A) {
if(A.length === 1 || A.length === 2) return true
let max = A[0]
for(let i = 0, len = A.length; i < len - 2; i++) {
max = Math.max(max, A[i]>
if(max > A[i + 2]) return false
}
return true;
};
Input
nums = [1,0,2]
Output
true
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isIdealPermutation(self, A):
for i, num in enumerate(A):
if not (i - 1 <= num <= i + 1): return False
return True
Input
nums = [1,0,2]
Output
true