Max Chunks to Make Sorted I


@jay It is O(N) as it is only making one pass through the array and the max function also takes only 2 arguments, not the whole array.

At least give us a shoutout bro.
https://discuss.leetcode.com/topic/117863/maxchunkstomakesorted/4

@alphaCeleritate I felt readers would not learn anything more by including those solutions here as they were too similar and messier to the O(N) Approach #1 solution here. The Approach #1 here was written before the contest even started.

@jay It is O(N) for max([a list of n elements]) in general, but I think in this case it always compares only 2 elements i and ma. I think we could consider that as O(1) time complexity. Therefore, for the nelement loop we have O(N) in total.

@2517997244GUAN [4,5,6,3] is not a valid case as it problem statement clearly mentions that array a permutation of [0, 1, ..., arr.length  1]

An array cannot be a permuted 0:n if its length is smaller than its maximal+1. Taking advantage of this insight, there is a lengthier but more efficient approach (still O(n) though):
def maxChunksToSorted(self, arr): if not arr: return(0) ix_now, max_now, count = 0, arr[0], 0 while True: if max_now == ix_now: count += 1 if ix_now == len(arr)1: break else: max_now = max(max_now, arr[ix_now+1]) ix_now += 1 else: tmp = max_now max_now = max(max_now, max(arr[(ix_now+1):(max_now+1)])) ix_now = tmp return(count)