274. Check if an Array Is a Stack Permutation of Another

Given two arrays of n integers, 'pushed' (the order elements are pushed onto an initially empty stack) and 'popped' (a candidate order of popping them all back off), determine whether 'popped' is achievable - i.e. whether there's some valid interleaving of pushes (always in the given order) and pops that produces exactly that popped sequence. Print 'Yes' if so, otherwise 'No'.

Input: The first line contains an integer n. The second line contains n space-separated distinct integers - the pushed order. The third line contains n space-separated integers - the candidate popped order. Output: Print 'Yes' if the popped sequence is achievable from the pushed order, otherwise print 'No'.

1 <= n <= 10^5, all values in each array are distinct

This is a great example of 'just simulate it directly, greedily' being the CORRECT and efficient approach - not every stack-related problem needs a clever monotonic-stack trick; sometimes direct simulation with a simple greedy rule is exactly right.

Given a 'pushed' order and a candidate 'popped' order, check if the popped order is actually achievable through some valid sequence of pushes and pops. Brute force: Try every possible interleaving of push and pop operations directly and check if any produces the exact 'popped' sequence - this is combinatorially expensive, impractical to search exhaustively. Optimised: The GREEDY rule 'always pop whenever the top matches the next expected popped value' is provably correct and never needs backtracking - if a pop is possible and matches, doing it immediately can never hurt future matching, since delaying it would only ever complicate the sequence further with no benefit.

Instead of allocating a separate stack, reuse the 'pushed' array itself as scratch space: maintain a pointer marking the current stack top within that same array, overwriting already-consumed slots as elements are popped off logically. The same push/pop-when-matching logic as the explicit-stack approach applies, but since 'pushed' is available to modify (or is being consumed anyway), no extra O(n) auxiliary stack allocation is needed, cutting the extra space to O(1) beyond the input and output. Time: O(n) Space: O(1) extra

Use a separate auxiliary stack and an index into 'popped'. Iterate through 'pushed', pushing each element onto the stack, and after every push, while the stack is non-empty and its top equals the next unmatched element of 'popped', pop it and advance the popped index. At the end, 'popped' is achievable exactly when the stack ends up empty. This greedy simulation is correct because a stack only ever needs to pop when it can, and it replaces the exponential search with one linear pass. Time: O(n) Space: O(n)

Recursively explore every valid way to interleave the fixed push order with pop actions: at each recursive state, either push the next element from 'pushed' onto a simulated stack or, if the simulated stack's top matches the next expected element of 'popped', pop it, and try both branches when both are legal. If any interleaving fully reproduces 'popped', answer yes. This explores an exponential number of interleavings (bounded by a Catalan-like number) even though the answer can be determined greedily. Time: O(2^n) Space: O(n)

1. Simulate it directly: push elements from 'pushed', one at a time, onto an auxiliary stack. 2. After EVERY push, check if the stack's current top matches the NEXT unmatched element of 'popped' - if so, pop it (and keep checking the new top against the following element of 'popped', repeatedly). 3. If you can process all of 'pushed' this way and match off every element of 'popped' in order, it's achievable - answer Yes.

Time: O(n) - each element is pushed once and popped at most once across the whole simulation. Space: O(n) in the worst case, for the auxiliary stack.

n = 1 (trivially achievable); popped equal to pushed reversed, which is always achievable (as in the example); a popped order that's impossible given the push order; n up to 10^5 for performance.

Be ready to justify WHY the greedy 'pop immediately when it matches' rule never needs backtracking - this is the single insight that turns what looks like it might require exploring many possibilities into a simple, deterministic single-pass simulation.