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 < 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:

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.length
  • 1 <= n <= 105
  • 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].

 

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;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,0,2]

Output

x
+
cmd
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
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,0,2]

Output

x
+
cmd
true
Advertisements

Demonstration


Previous
#773 Leetcode Sliding Puzzle Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#777 Leetcode Swap Adjacent in LR String Solution in C, C++, Java, JavaScript, Python, C# Leetcode