Validate Stack Sequences - Practice Coding Problems

Validate Stack Sequences - Problem

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

The arrays represent the order in which elements were pushed onto the stack and the order in which they were popped from the stack. Your task is to determine if the pop sequence is valid given the push sequence.

Key Points:

Stack follows LIFO (Last In, First Out) principle
All values in both arrays are distinct
Both arrays have the same length

Input & Output

Example 1 — Valid Sequence

$ Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

› Output: true

💡 Note: Push 1,2,3,4 → Pop 4 → Push 5 → Pop 5,3,2,1. This sequence is valid.

Example 2 — Invalid Sequence

$ Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

› Output: false

💡 Note: After popping 4,3, we need to pop 5, but 5 hasn't been pushed yet when 3 was on top.

Example 3 — Simple Case

$ Input: pushed = [1,2], popped = [2,1]

› Output: true

💡 Note: Push 1,2 → Pop 2,1. Simple LIFO order works.

Constraints

1 ≤ pushed.length ≤ 1000
0 ≤ pushed[i] ≤ 1000
All elements in pushed are unique
popped.length == pushed.length
popped is a permutation of pushed

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: pushed=[1,2,3,4,5], popped=[4,5,3,2,1]

Simulate

Use stack to mimic push/pop operations

Validate

Check if sequence is achievable

Key Takeaway

🎯 Key Insight: Use a stack to simulate the operations - if we can match the popped sequence exactly, it's valid

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to simulate the stack operations using an auxiliary stack. Push elements from the pushed array and greedily pop whenever the top matches the current element in popped array. Best approach is Stack Simulation with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^n)	O(n)	Try all possible interleavings of push and pop operations
Stack Simulation	O(n)	O(n)	Simulate the actual stack operations step by step

Brute Force Simulation — Algorithm Steps

Generate all possible push/pop sequences
Check if any sequence produces the target popped array
Return true if found, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Branch

At each step, try both push and pop operations

Recurse

Explore each possibility recursively

Backtrack

Undo operations and try other paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int* pushed, int* popped, int n, int pushIdx, int popIdx, int* stack, int stackSize) {
    if (popIdx == n) {
        return true;
    }
    
    // Try popping from stack
    if (stackSize > 0 && stack[stackSize-1] == popped[popIdx]) {
        int poppedVal = stack[stackSize-1];
        stackSize--;
        if (backtrack(pushed, popped, n, pushIdx, popIdx + 1, stack, stackSize)) {
            return true;
        }
        stack[stackSize] = poppedVal; // backtrack
        stackSize++;
    }
    
    // Try pushing next element
    if (pushIdx < n) {
        stack[stackSize] = pushed[pushIdx];
        if (backtrack(pushed, popped, n, pushIdx + 1, popIdx, stack, stackSize + 1)) {
            return true;
        }
    }
    
    return false;
}

bool solution(int* pushed, int* popped, int n) {
    int* stack = (int*)malloc(n * sizeof(int));
    bool result = backtrack(pushed, popped, n, 0, 0, stack, 0);
    free(stack);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int pushed[100], popped[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            pushed[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            popped[m++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    bool result = solution(pushed, popped, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential combinations of push/pop operations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and temporary storage

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler