Check if a Queue Can Be Sorted Using an Auxiliary Stack

You are given a queue containing a permutation of the integers 1 to N (each value appears exactly once), listed from front to back. Using exactly one auxiliary stack, you want to output the values in strictly increasing order (1, 2, 3, ..., N). At each step you may either remove the front element of the queue and push it onto the stack, or, if the value on top of the stack equals the next value you still need to output, pop it and output it. You must always take the next expected value from the stack the moment it becomes available. Determine whether it is possible to output all N values in increasing order this way.

Input: The first line contains the integer N. The second line contains N space-separated distinct integers from 1 to N, the queue's contents from front to back. Output: Print "YES" if the queue can be emptied in increasing sorted order using a single auxiliary stack as described, otherwise print "NO".

1 <= N <= 100000; the input is guaranteed to be a permutation of 1..N

This combines a QUEUE's FIFO input order with a STACK's LIFO temporary storage - recognizing exactly which values the stack's LIFO nature would trap incorrectly is the key insight, not just mechanically simulating the process.

Check whether a queue containing a shuffled permutation of 1 to N can be output in perfect increasing order, using only one extra stack for temporary holding. Brute force: Try every possible sequence of push/pop decisions directly and check if any produces the fully sorted output - this branches combinatorially, impractical to search exhaustively. Optimised: The greedy rule (output immediately when possible, and check that a value about to be pushed isn't SMALLER than the stack's current top) directly and provably detects impossibility the moment it would occur - a smaller value trapped beneath a larger one on the stack can never be retrieved before that larger one, since a stack is LIFO, so this single check is both necessary and sufficient.

1. Track the NEXT value you still need to output, starting at 1. 2. Whenever the FRONT of the queue equals the next needed value, output it directly - no stack needed for it. 3. Otherwise, PUSH it onto the stack - but if the stack's CURRENT top is SMALLER than the value you're about to push, the arrangement is IMPOSSIBLE: that smaller value would get permanently stuck underneath a value that must come out after it.

Time: O(n) - one single pass through the queue, with O(1) stack operations. Space: O(n) in the worst case, for the auxiliary stack.

N = 1 is always "YES"; an already sorted queue is always "YES"; a fully reversed queue (N, N-1, ..., 1) is also always sortable this way.

Be ready to explain PRECISELY why a smaller value under a larger one on the stack makes the arrangement impossible - this is the entire crux of the problem, and articulating it clearly (rather than just applying the check) is what interviewers are listening for.