# Max Chunks to Make Sorted I

• Isn't this O(N^2) time for python?

• @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.

• @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.

• Here the space complexity is O(1)

• 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]

• It is a clever solution!

• 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)
``````

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