Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

775. Global and Local Inversions - Leetcode Solution

Code Implementation

class Solution:
    def isIdealPermutation(self, A):
        # For local == global, no element can be more than 1 away from its sorted position
        for i, num in enumerate(A):
            if abs(num - i) > 1:
                return False
        return True
      
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;
    }
};
      
class Solution {
    public boolean isIdealPermutation(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (Math.abs(A[i] - i) > 1) return false;
        }
        return true;
    }
}
      
var isIdealPermutation = function(A) {
    for (let i = 0; i < A.length; ++i) {
        if (Math.abs(A[i] - i) > 1) return false;
    }
    return true;
};

Problem Description

Given an array A consisting of distinct integers from 0 to n-1 (a permutation), we define:

  • A global inversion is a pair (i, j) such that 0 <= i < j < n and A[i] > A[j].
  • A local inversion is a pair (i, i+1) such that A[i] > A[i+1].
Your task is to determine if every global inversion is also a local inversion in A. In other words, the number of global inversions is equal to the number of local inversions.

Constraints:

  • 1 <= A.length <= 10^5
  • All elements in A are unique and in the range [0, A.length - 1]

Thought Process

Let's break down what the problem is asking:

  • A local inversion is a special case of a global inversion, where the two indices are next to each other.
  • There can be global inversions that are not local (i.e., where j - i > 1).
  • We need to check if there are no global inversions that are not also local.
The brute-force approach would be to count all global and local inversions, but this is too slow for large arrays (quadratic time).
The key insight is to realize that a non-local global inversion occurs if some number is "far" from its sorted position. For example, if A[i] is more than 1 away from i, it must have swapped with a non-adjacent element, creating a non-local inversion.
Our goal is to check if every element is at most 1 position away from its sorted position.

Solution Approach

  • Since A is a permutation of 0 to n-1, the "correct" position for k is k itself.
  • For each index i, check if A[i] is at most 1 away from i (i.e., abs(A[i] - i) <= 1).
  • If we ever find an element with abs(A[i] - i) > 1, then there must be a global inversion that is not local.
  • Otherwise, all inversions are local, and we can return True.

This approach is efficient and only requires a single pass through the array.

Example Walkthrough

Let's use the array A = [1, 0, 2]:

  • At i=0: A[0]=1, abs(1-0)=1 (OK)
  • At i=1: A[1]=0, abs(0-1)=1 (OK)
  • At i=2: A[2]=2, abs(2-2)=0 (OK)
All elements are at most 1 away from their sorted position, so the answer is True.
Now, consider A = [1, 2, 0]:
  • At i=0: A[0]=1, abs(1-0)=1 (OK)
  • At i=1: A[1]=2, abs(2-1)=1 (OK)
  • At i=2: A[2]=0, abs(0-2)=2 (Not OK)
Here, 0 is two positions away from where it should be, so there is a non-local inversion. The answer is False.

Time and Space Complexity

  • Brute-force approach: For every pair (i, j), check if A[i] > A[j]. This is O(n^2) time, which is too slow for large arrays.
  • Optimized approach: We only need to scan the array once and check abs(A[i] - i) <= 1 for each i. This is O(n) time and O(1) space.

Summary

The problem asks whether all global inversions are also local. By realizing that this is only possible when no element is more than one position from its sorted place, we can efficiently solve the problem in a single pass. This elegant solution leverages the properties of permutations and avoids unnecessary counting or nested loops.