Build an Array With Stack Operations

medium stack simulation array

Problem

You are given a strictly increasing list of integers target whose values come from the stream 1, 2, 3, …, n. Using only the operations "Push" (read the next number from the stream onto a stack) and "Pop" (remove the top of the stack), produce a sequence of operations so that the stack ends up exactly equal to target. Stop reading once every number in target has been placed, and return the list of operations used.

Inputtarget = [1, 3], n = 3

Output["Push", "Push", "Pop", "Push"]

Read 1 → Push (keep). Read 2 → Push then Pop (2 is not in target). Read 3 → Push (keep). Stack is now [1, 3].

target (comma-separated)

def build_array(target, n):
    ops = []
    cur = 1
    for want in target:
        while cur < want:
            ops.append("Push")
            ops.append("Pop")
            cur += 1
        ops.append("Push")
        cur += 1
    return ops

function buildArray(target, n) {
  const ops = [];
  let cur = 1;
  for (const want of target) {
    while (cur < want) {
      ops.push("Push");
      ops.push("Pop");
      cur += 1;
    }
    ops.push("Push");
    cur += 1;
  }
  return ops;
}

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> ops = new ArrayList<>();
        int cur = 1;
        for (int want : target) {
            while (cur < want) {
                ops.add("Push");
                ops.add("Pop");
                cur += 1;
            }
            ops.add("Push");
            cur += 1;
        }
        return ops;
    }
}

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> ops;
    int cur = 1;
    for (int want : target) {
        while (cur < want) {
            ops.push_back("Push");
            ops.push_back("Pop");
            cur += 1;
        }
        ops.push_back("Push");
        cur += 1;
    }
    return ops;
}

Explanation

The numbers arrive in order 1, 2, 3, … and we can only act on the next one in line, so the natural plan is to walk that stream from 1 upward and decide what to do with each value as it shows up.

Keep a pointer cur for the number currently coming off the stream. For every value want in target (left to right), there may be a gap of numbers between cur and want that we do not want to keep. Each of those unwanted numbers still has to be read, so we Push it and then immediately Pop it — it lands on the stack and is thrown away in the same breath.

Once cur finally reaches want, that number belongs in the answer, so we Push it and leave it there. Because target is strictly increasing and its largest value is at most n, we never overshoot; we simply stop the moment the last target value has been pushed.

Example: target = [1, 3], n = 3. Start at cur = 1. First want = 1: no gap, just Push 1. Move to want = 3: cur is now 2, which is less than 3, so Push 2 then Pop 2 to skip it; now Push 3. The operation list is ["Push", "Push", "Pop", "Push"] and the stack is [1, 3].

Every number from 1 up to the last target value is touched at most twice (one Push, maybe one Pop), so the work is linear in that range.

Time: O(n) Space: O(n)