775. An alternative solution for a more general case. O(n log n)

  • 0


    I'd like to share a solution for a generous case, where A is an arbitrary array. The time complexity is O(NlogN).

    class Solution:
        def isIdealPermutation(self, A):
            :type A: List[int]
            :rtype: bool
            def find_local(A):
                cnt = 0;
                for i,j in zip(A[:],A[1:]):
                    if j < i:
                        cnt += 1
                return cnt
            def find_global(A):
                cnt = 0;
                l = []
                for i in A:
                    x = bisect.bisect_right(l, i)
                    cnt += len(l) - x
                    bisect.insort(l, i)
                return cnt
            return find_local(A) == find_global(A)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.