Max Chunks to Make Sorted


  • 0

    Click here to see the full article post


  • 0
    C
    This post is deleted!

  • 0
    L

    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();
        }
    

  • 0
    H
    This post is deleted!

  • 1
    G

    Using a stack and storing the max of chunk, the min of a chunk and the max left of this chunk, we can reduce the runtime to O(N).


  • 0

    @galster Can you explain a little more?


  • 1
    L

    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;
    }
    

    }


  • 1
    A

    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;
    

  • 1
    H

    @lookforlohith this failed in

    [4,2,2,1,1]
    

    case


  • 0
    A

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


  • 0
    L

    @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


  • 0
    L

    @han9758
    thanks for identifying that as a corner case, I still think its a o(n) and here is my modification

    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;
    	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;
    }
    

    }


  • 0
    G

    @awice

    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();
        }
    };
    

  • 0

    In the last two solutions this fails for [2,1,3,4,4] (Max Chunks to Make Sorted II), but I think it was intended to be an O(N) solution for it?


  • 0

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


  • 0
    M

    Python code failed in python3
    TypeError: unorderable types: tuple() > NoneType()


  • 0

    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.


  • 0

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


  • 0

    @termi23321-yahoo.com, it returns 1 as expected. You should probably run and see.


  • 0
    2

    @benevolent, So great! Thanks for your excellent solution.


Log in to reply
 

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