{"id":9616,"date":"2022-09-12T09:53:55","date_gmt":"2022-09-12T09:53:55","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9616"},"modified":"2022-10-03T03:59:52","modified_gmt":"2022-10-03T03:59:52","slug":"check-if-an-array-is-stack-sortable","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/check-if-an-array-is-stack-sortable\/","title":{"rendered":"Check if an Array is Stack Sortable"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

You will be given an array A of integers containing N elements. All the elements inside the array are unique and in the range of 1 to N, where both 1 and N are inclusive.
\nYou have to tell whether this array<\/a> A is stack sortable or not.<\/p>\n

An array A is said to be stack sortable if all the elements of array A can be moved to an array B by using an auxiliary stack when only the given operations are allowed.<\/p>\n

    \n
  1. Operation 1:<\/strong> Removing an element from the front of array A and inserting it into the Stack.<\/li>\n
  2. Operation 2:<\/strong> Removing the element (top) from the stack and appending it to the end of array B.<\/li>\n<\/ol>\n

    So, after moving all the elements of array A to array B using the above operations, if array B is sorted in ascending order, array A can be said to be stack sortable else it cannot be called stack sortable.<\/p>\n

    Example<\/strong><\/p>\n

    Consider the array A, B, and the stack as shown below.<\/p>\n

    \"\"<\/p>\n

    Now, let us try to see if all the elements of array A can be moved to array B such that array B is sorted in ascending order.<\/p>\n

      \n
    1. Operation 1<\/li>\n<\/ol>\n

      \"\"<\/p>\n

        \n
      1. Operation 1 (Now element 1 is at the front of the array as 4 has been removed.)<\/li>\n<\/ol>\n

        \"\"<\/p>\n

          \n
        1. Operation 2 (Remove 1 from the stack and insert it into the array)<\/li>\n<\/ol>\n

          \"\"<\/p>\n

            \n
          1. Operation 1 (Remove 2 from the front and add it to the top of the stack)<\/li>\n<\/ol>\n

            \"\"<\/p>\n

              \n
            1. Operation 2 (Remove 2 from the stack and add it to the array B).<\/li>\n<\/ol>\n

              \"\"<\/p>\n

                \n
              1. Operation 1 (Add 3 into the stack)<\/li>\n<\/ol>\n

                \"\"<\/p>\n

                  \n
                1. Operation 2 (Remove 3 from the stack and add it to the array B)<\/li>\n<\/ol>\n

                  \"\"<\/p>\n

                    \n
                  1. Operation 2 (Remove 4 from the stack and add it to the array B)<\/li>\n<\/ol>\n

                    \"\"<\/p>\n

                    So, as you can see, we have successfully filled array B in ascending order by removing all the elements of array A and performing just the 2 allowed operations. Hence, array A is stack sortable.<\/p>\n

                    Approach<\/h3>\n

                    The approach is purely observation based and we can derive the logic for our observation. <\/p>\n

                    From the sequence of operations performed in the above example, we can observe that:<\/p>\n

                      \n
                    1. Pushing an element into the stack is only possible when either the stack is empty or the current element that we want to push into the stack is less than the value at the top of the stack.<\/li>\n
                    2. Popping an element from the stack is only possible if the element present at the top of the stack is the next element in the sequence to the last element present in the array B i.e. top of the stack = B[end] + 1. This is because the array B has to maintain the sequence {1,2,3 \u2026. N}.<\/li>\n<\/ol>\n

                      So, we will continue to perform there operations till all the elements of the array are processed and till the stack is not empty. However, in between the procedure, if we are not able to push the starting element of the array A into the stack and we can\u2019t pop an element from the stack as well, then the array A will be not stack sortable. <\/p>\n

                      So, since we have already seen in the example aboe, a case where we found that array A was stack sortable, let us now see a case when we find that the array A is not stack sortable. For this, consider the example given below.<\/p>\n

                      \"\"<\/p>\n

                      We have initially filled the array B with 0s. (No need to do this in Java as they are by default 0s. In C++, these may be garbage values hence we will fill them.)<\/p>\n

                      So, let us try to find out whether the array A is stack sortable or not using the 2 points discussed above.
                      \nFirst, since the stack is empty, we will perform operation 1 i.e. push an element (front of the array A) into the stack. (Also, initially, the end pointer will be at index 0)<\/p>\n

                      \"\"<\/p>\n

                      Now, we move at the next element 3. Since the current element is larger than the top of the stack, we cannot push it into the stack. Also, 2 which is at the top of the stack is not equal to B[end] + 1 as B[end] +1 = B[0] + 1 = 0 + 1 = 1.<\/p>\n

                      Hence, we can\u2019t push the element into the stack and can\u2019t place it into the array either. So, the array A is not stack sortable.<\/p>\n

                      Now that we have discussed the complete procedure, let us write the code for the same.<\/p>\n\t\t\t\t\t\t