Click here to see the full article post
@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.
@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 n-element loop we have O(N) in total.
But I'm a little confused about the solution.Let me take a case [4, 5, 6, 3],The solution will print 3, but as we can analyze, the correct answer should be 1.
@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 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)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.