Build an Array With Stack Operations - Practice Coding Problems

Build an Array With Stack Operations - Problem

You are given an integer array target and an integer n.

You have an empty stack with the two following operations:

"Push": pushes an integer to the top of the stack.
"Pop": removes the integer on the top of the stack.

You also have a stream of the integers in the range [1, n].

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:

If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
If the stack is not empty, pop the integer at the top of the stack.
If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.

Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

Input & Output

Example 1 — Basic Case

$ Input: target = [1,3], n = 5

› Output: ["Push","Push","Pop","Push"]

💡 Note: Stream is [1,2,3,4,5]. Push 1 (matches target[0]), Push 2 (doesn't match target[1]), Pop 2, Push 3 (matches target[1]). Target complete.

Example 2 — Consecutive Numbers

$ Input: target = [1,2,3], n = 3

› Output: ["Push","Push","Push"]

💡 Note: Target contains consecutive numbers 1,2,3 from start of stream. Just push each number without any pops needed.

Example 3 — Single Element

$ Input: target = [1], n = 1

› Output: ["Push"]

💡 Note: Target has only one element which is 1. Stream starts with 1, so just push it once and we're done.

Constraints

1 ≤ target.length ≤ 100
1 ≤ target[i] ≤ n ≤ 100
1 ≤ n ≤ 100
target is strictly increasing

Visualization

Tap to expand

Understanding the Visualization

Input

Stream [1,2,3,4,5] and target [1,3]

Process

Use Push/Pop operations to build target

Output

Sequence of operations: ["Push","Push","Pop","Push"]

Key Takeaway

🎯 Key Insight: Process stream sequentially, push every number but immediately pop those not needed in target

Asked in

a Amazon 15 M Microsoft 12

The key insight is to simulate the stack operations by processing the stream sequentially. For each number from 1 to n, push it onto the stack. If it matches the next expected target element, keep it; otherwise, pop it immediately. Best approach uses early termination optimization. Time: O(max(target)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Early Termination Optimization	O(max(target))	O(1)	Same approach but stop processing as soon as target is complete
Sequential Stream Processing	O(n)	O(1)	Process each number from 1 to n, push if needed in target, pop if not

Early Termination Optimization — Algorithm Steps

Process numbers 1, 2, 3... in order
For each number: Push it to stack
If number matches next target element, keep it
If number doesn't match, Pop it immediately
Stop immediately when target array is complete

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Progress

Monitor how many target elements we've matched

Early Exit

Stop as soon as targetIndex equals target.length

Efficiency

Avoid processing remaining stream numbers

Code -

solution.c — C

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

char** solution(int* target, int targetSize, int n, int* returnSize) {
    char** operations = malloc(2 * n * sizeof(char*));
    int opCount = 0;
    int targetIndex = 0;
    int current = 1;
    
    while (targetIndex < targetSize && current <= n) {
        operations[opCount] = malloc(5 * sizeof(char));
        strcpy(operations[opCount], "Push");
        opCount++;
        
        if (current == target[targetIndex]) {
            targetIndex++;
        } else {
            operations[opCount] = malloc(4 * sizeof(char));
            strcpy(operations[opCount], "Pop");
            opCount++;
        }
        
        current++;
    }
    
    *returnSize = opCount;
    return operations;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse target array
    int target[100];
    int targetSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        target[targetSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int n;
    scanf("%d", &n);
    
    int returnSize;
    char** result = solution(target, targetSize, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(target))

Loop runs until we reach the largest number in target, not full n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for tracking, output list not counted

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 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

Early Termination Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler