Max Chunks to Make Sorted


A O(N^2) solution in C++.
int maxChunksToSorted(vector<int>& arr) { if (arr.size() == 0) return 0; stack<int> st; st.push(arr[0]); for (int i = 1; i < arr.size(); i++) { if (st.top() <= arr[i]) { // may be start of the new chunk. st.push(arr[i]); } else { // Save the current top int maxSoFar = st.top(); while (!st.empty()) { // repeatedly pop off the elements till // we get one that is less than or equal // to the current element. if (st.top() > arr[i]) { st.pop(); } else { break; } } st.push(maxSoFar); } } return st.size(); }


O(n) solution
I am not sure If i misunderstood the problem statement, but It seems like a problem where we count the minimas. It works well for both the above examples and I would appreciate if any one showed me a case where I mistook the problemstatement
public class Solution {
public static void main(String str[]){ int[] arr = {2,1,3,4,4}; System.out.println(maxChunksToSorted(arr)); } public static int maxChunksToSorted(int[] arr) { if (arr == null) return 1; if (arr.length == 1) return 1; int count = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] >= arr[i  1]) { count++; } } return count + 1; }
}

Here is a O(n) solution to this problem. Since we know that each number is only seen once we know that once we find the right index of where the chunk that number belongs to should be.
arr = [4,3,2,1,0]
The 4 should be in location 4, once it is there.arr = [1,0,2,3,4]
The 1 should be in location 1, so we increment until location 1 and check to see if there are any other larger numbers within our chunk.arr = [1,2,0,3,4]
The 1 should be in location 1
we increment to location 1>the 2 should be in location 2 so we increment until location 2. Now the chunk is ordered.
The problem could be more interesting if duplicates were allowed.int maxChunksToSorted(vector<int>& arr) { int cur =arr[0], retVal=0, n=arr.size(); for(int i=0; i<n; i++){ while(i<n){ cur=max(cur, arr[i]); if(cur<=i) break; i++; } retVal++; } return retVal;


@han9758 that is a test case for Max Chunks to Make Sorted II, this problem states that all values in the array are unique.

@han9758
awesome han !! Im thinking that [4,2,2] [1] [1] is the answer? but sorting them and concatenating them would give 2 2 4 1 1 which is not sorted and the question doesnot clearly explain it, but thanks

@han9758
thanks for identifying that as a corner case, I still think its a o(n) and here is my modificationpublic class Solution {
public static void main(String str[]){ int[] arr = {2,1,3,4,4}; System.out.println(maxChunksToSorted(arr)); } public static int maxChunksToSorted(int[] arr) { if (arr == null) return 1; if (arr.length == 1) return 1; int count = 0; boolean isReducing = false; for (int i = 1; i < arr.length; i++) { if (arr[i] > arr[i  1]) { count++; isReducing = false; }if (arr[i] == arr[i  1]) { if(!isReducing) count++; }else{ isReducing = true; } } return count + 1; }
}

class Solution { public: struct Triplet{ int start; int end; int maxSoFar; }; using T=Triplet; int maxChunksToSorted(vector<int>& arr) { vector<T> stack; if(arr.empty()){ return 0; } stack.push_back({arr[0],arr[0],arr[0]}); for(int i = 1; i < arr.size();){ if(arr[i] > stack.back().start){ stack.push_back({arr[i],arr[i],stack.back().start}); i++; } else{ if(arr[i] > stack.back().maxSoFar  stack.size() == 1){ stack.back().end = min(arr[i],stack.back().end); i++; } else{ auto top = stack.back(); stack.pop_back(); stack.back().start = top.start; stack.back().end = min(stack.back().end,arr[i]); } } } return stack.size(); } };

@awice Maybe it's just meant for version I of the problem. This topic is titled "Max Chunks to Make Sorted", after all. Not version II.
The articles/topics/links are messed up, for example the "here" link in your first post goes to an invalid URL. And the "View original thread" link on the version II page links to this topic here. And version I is called Max Chunks To Make Sorted (no "I") while its article calls it Max Chunks to Make Sorted I.

I think it can be solved in a simple way (with O(N) space and time complexity). I got this approach accepted.
Suppose we are at position k and want to know if we can split it into two chunks at k. Can we do that? If the largest number from arr[0] up until and including arr[k] is less than or equal to the smallest number from arr[k+1] to the end, then we can it split into two valid chunks (proof at the bottom). If we can split, we increase our answer and update our maximum.
To know the minimum element from k to arr.Length 1, we can just precompute from right to left and query it in O(1) later. Here is my accepted answer:
public int MaxChunksToSorted(int[] arr) { int[] min = new int[arr.Length]; min[arr.Length 1] = arr[arr.Length 1]; for(int i = arr.Length  2; i >= 0; i) { min[i] = Math.Min(min[i + 1], arr[i]); } int max = arr[0]; int answer = 1; for(int i = 0; i < arr.Length  1; i++) { if(max <= min[i + 1]) { answer++; } max = Math.Max(max, arr[i + 1]); } return answer; }
Proof:
We asserted earlier that the largest number of the left chunk must be less than or equal to the smallest number in the right chunk. This is illustrated below:left right [......max] [min......]
if max is greater than min, then the array cannot be a sorted one after they are concatenated. So it must hold that max in the left is either smaller or the same as the min element on the right chunk.

@benevolent, looking at your code, it will return 4 chunks for [ 4, 2, 2, 1, 1, 1, 1 ], whereas the correct number is 1.

