Skills101
← All coding problems

Max Chunks to Make Sorted

mediumArrays & Prefix Sums+20 XPTime limit 2s

Split the array into consecutive chunks (every element in exactly one chunk). Then sort each chunk on its own and put the chunks back in their original order. You want the final array to be fully sorted in non-decreasing order.

What is the largest number of chunks you can use? (The array may contain repeated values.)

Input:

  • line 1: n
  • line 2: n integers

Output: the maximum number of chunks.

Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.

Think about it: you may cut after position i exactly when everything on the left is ≤ everything on the right — that is, max(a[0..i]) ≤ min(a[i+1..n−1]). Precompute suffix minimums, sweep a running prefix maximum, and count the valid cuts (plus the last chunk).

Sample input 1

5
2 1 3 4 4

Sample output 1

4

Sample input 2

5
5 4 3 2 1

Sample output 2

1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.