Code Logo

Build Array With Stack Operations

Published at23 Jul 2026
Created by
Easy 0 views
Like0

You are given a target array of distinct integers sorted in ascending order, and an integer n. You have an empty stack and you read numbers from 1 to n in order. For each number, you must push it onto the stack. If the number is in the target array, you keep it. If it's not in the target array, you must pop it immediately after pushing. Record each operation as "Push" or "Pop". Return the list of operations needed to build the target array.

This problem simulates building an array using stack operations. It tests whether you understand that a stack only allows pushing and popping, and that elements not in the target must be removed immediately.

For example, target = [1,3], n = 3: Read 1 → Push (1 is in target). Read 2 → Push then Pop (2 is not in target). Read 3 → Push (3 is in target). Result: ["Push","Push","Pop","Push"].

The maximum number to consider is the last element of the target array, not n. If n is larger than the last target element, we stop at the last target element because further numbers would always be pushed and popped unnecessarily. The operations are recorded in order and returned as a list of strings.

This problem is commonly asked in entry-level technical interviews to assess understanding of fundamental stack behavior and array construction patterns. The solution is straightforward once you recognize that the stack operations map directly to the problem requirements.

Example Input & Output

Example 1
Input
[1,3], 3
Output
["Push","Push","Pop","Push"]
Explanation

1: Push. 2: Push+Pop. 3: Push.

Example 2
Input
[1], 1
Output
["Push"]
Explanation

Only 1.

Example 3
Input
[1,2], 3
Output
["Push","Push","Push"]
Explanation

1,2 all in target.

Algorithm Flow

Recommendation Algorithm Flow for Build Array With Stack Operations
Recommendation Algorithm Flow for Build Array With Stack Operations

Solution Approach

Iterate i from 1 to n. Push "Push". If i is not in target set, also push "Pop". Return the operations list.

function solution(target, n) {
  var set = {};
  for (var i = 0; i < target.length; i++) set[target[i]] = true;
  var result = [];
  for (var i = 1; i <= target[target.length-1]; i++) {
    result.push("Push");
    if (!set[i]) result.push("Pop");
  }
  return result;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public List<String> solution(int[] target, int n) {
        Set<Integer> set = new HashSet<>();
        for (int x : target) set.add(x);
        List<String> result = new ArrayList<>();
        for (int i = 1; i <= target[target.length-1]; i++) {
            result.add("Push");
            if (!set.contains(i)) result.add("Pop");
        }
        return result;
    }
}