Problem statement

https://leetcode.com/problems/global-and-local-inversions/

Solution

One way to solve it is to just find all number of permutations either in O(n^2) bruteforce or O(n * log n) using merge sort or Sorted List.

However here we do not need to do it and we can solve it in O(n) time. Let us keep level, this is maximum among first i-1 values. If we consider i+1-th number, than it need to be greater than level to return True. Indeed, if it is not the case, than we have at least one inversion which is not local, with gap 2 or more. So if at any moment this condition do not hold, we return False and finish our program.

From the other point of view, if at each step we have A[i+1] > max(A[0], A[1], ... A[i-1]), it means that we can not have not-local inversions: for each two indexes j and k, such that j >= k + 2, we get A[j] > A[k], which is exaclty definition of not-local inversion.

So, what we checked here is that our condition is sufficient and enough to check that number of global inversions is equal to number of local inverstions.

Complexity

Time complexity is $\mathcal{O}(n)$ as we discussed, space complexity is $\mathcal{O}(1)$.

Code

class Solution:
    def isIdealPermutation(self, A):
        level = -float("inf")
        n = len(A)
        for i in range(1, n):
            if A[i] < level: 
                return False
            else:
                level = max(level, A[i-1])
                
        return True

Remark

We can also notice that we could only place i at A[i-1], A[i] or A[i+1] and check it again in $\mathcal{O}(n)$ time.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0775