Max chunks to
make it sorted

Cut into the most pieces that sort independently to the same result

Split the array into contiguous chunks, sort each chunk on its own, concatenate — the result must equal the fully sorted array. Maximize the number of chunks. For [2,1,3,4,4], the finest valid split is [2,1] | [3] | [4] | [4] → sorts to [1,2,3,4,4], so the answer is 4.

max(left) ≤ min(right)

You don't need to compare every left-right pair. Extremes summarize everything: if the largest value on the left is ≤ the smallest value on the right, then every left value is ≤ every right value. Any left x ≤ max(left) ≤ min(right) ≤ y any right. So the cut after index i is safe exactly when:

It must be ≤, not < — this is the "II" variant with duplicates. [2] | [2] is a perfectly valid two-chunk split, and 2 ≤ 2 allows it.

A boundary depends on aggregates, not neighbors

Tempting shortcut: cut wherever arr[i] ≤ arr[i+1]. It breaks. In [5,1,4,3,6], at index 1 we have 1 ≤ 4, but cutting [5,1] | [4,3,6] fails — the left max is 5 and the right min is 3, and 5 > 3. The stranded 5 belongs after the 3. Local order can't see a large value hiding earlier in the prefix; you need the aggregate.

prefixMax above, suffixMin below

Type an array (or pick one). The top row is prefixMax (teal, running max from the left), the middle is the array, the bottom is suffixMin (terracotta, running min from the right). At each gap, the comparison prefixMax[i] vs suffixMin[i+1] lights a solid teal cut when safe, a faint mark when blocked. Chunks = safe cuts + 1.

Try 5 4 3 2 1 (no safe cut → 1 chunk), 1 2 3 4 (every gap safe → 4), or 2 4 1 (a small tail forces one big chunk).

The sample, boundary by boundary

For [2,1,3,4,4]: prefixMax = [2,2,3,4,4], suffixMin = [1,1,3,4,4].

Three safe cuts → four chunks. Every safe boundary can be taken at once: each one guarantees left ≤ right independently, so they never conflict. That's why the answer is just count of safe cuts + 1 — greedy, no DP needed.

One suffix array, a rolling prefix max

int maxChunksToSorted(int[] arr) {
    int n = arr.length;
    int[] suffixMin = new int[n];
    suffixMin[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; i--)
        suffixMin[i] = Math.min(arr[i], suffixMin[i+1]);

    int chunks = 1, prefixMax = Integer.MIN_VALUE;
    for (int i = 0; i < n-1; i++) {
        prefixMax = Math.max(prefixMax, arr[i]);
        if (prefixMax <= suffixMin[i+1]) chunks++;   // safe boundary
    }
    return chunks;
}

Build the suffix-min array once (O(N)), then sweep left keeping a rolling max — no need to store the full prefix array. O(N) time, O(N) space. Start chunks = 1 because an uncut array is already one chunk.

A monotonic stack that merges bad chunks

Same answer, opposite lens. Keep a stack where each entry is one candidate chunk's maximum. A new value ≥ the top starts a fresh chunk. A smaller value can't stand alone after a taller chunk, so you pop the merged max, keep popping every chunk whose max exceeds the newcomer, and push back the single largest — those chunks fuse into one. The stack's final size is the chunk count.

Deque<Integer> st = new ArrayDeque<>();
for (int v : arr) {
    if (st.isEmpty() || v >= st.peek()) st.push(v);
    else {
        int mergedMax = st.pop();
        while (!st.isEmpty() && st.peek() > v) st.pop();
        st.push(mergedMax);                // merged chunk keeps its ceiling
    }
}
return st.size();

Four ways this goes wrong

Characterize the operation instead of simulating it

The array never actually gets sorted in the solution. Instead you ask what would make independent sorting impossible: a large left value that belongs after a small right value — a cross-boundary inversion. A boundary is safe precisely when none exists, i.e. max(left) ≤ min(right).

It's the same habit behind next-permutation's descending-suffix scan: before simulating an expensive operation, find the condition that tells you whether it would succeed. That converts an exponential search into a linear pass.

Reconstruct it, don't memorize it

1. I want the most independently-sortable pieces.
2. Elements can't cross a cut, so left must already belong before right.
3. That's max(left) ≤ min(right) — extremes summarize all pairs.
4. Precompute prefix max and suffix min so each boundary is O(1).
5. Cut at every safe boundary; chunks = safe cuts + 1.