Leetcode 1441: Build an Array With Stack Operations

In this Leetcode problem we are given an integer n representing the list {1, 2, ..., n}, and an array int[] target. We are going to assume we have a stack and we are pushing 1, 2, ... and popping number so that we can arrive to target as a result. The question is, in what order should we push and pull so that we arrive at target?

Problem statement

Solution

We can notice that there is a simple way to push and pop to build the target array.

1. If i is in the array target, when we arrive there, push it.
2. If i is not in the array target, when we arrive there, push it and pop it so we remove it from the final result
3. Once we added all the numbers in target, we don’t need to push and pop the remaining integers, we can return the current list of commands instead.

These 3 cases are represented in the respective if/else statements in the following code:

class Solution {
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int current = 0;
        int p = target.length;
        for (int i = 1; i <= n; i++) {
            if (current < p) {
                if (target[current] == i) {
                    res.add("Push");
                    current++;
                } else {…