Sponsored
Sponsored
In this approach, we use two pointers: one to iterate over the stream numbers from 1 to n, and another to iterate over the target list. For each number in the range, if the number matches the current target number, we "Push" it to the stack. If it does not match, we "Push" and then "Pop". This way, we use the minimum operations to achieve the target stack.
Time complexity: O(n), where n is the range. Space complexity: O(m), where m is the number of operations stored.
1import java.util.*;
2
3public class BuildArray {
4 public List<String> buildArray(int[] target, int n) {
5 List<String> operations = new ArrayList<>();
6 int t = 0;
7 for (int i = 1; i <= n && t < target.length; ++i) {
8 operations.add("Push");
9 if (i != target[t]) {
10 operations.add("Pop");
11 } else {
12 ++t;
13 }
14 }
15 return operations;
16 }
17
18 public static void main(String[] args) {
19 BuildArray ba = new BuildArray();
20 int[] target = {1, 3};
21 int n = 3;
22 List<String> operations = ba.buildArray(target, n);
23 for (String operation : operations) {
24 System.out.println(operation);
25 }
26 }
27}This Java solution follows a similar logic, using an ArrayList to maintain a dynamic list of operations. For each number in the range, it checks the target array for a match, decides whether to just push or both push and pop.
This approach involves a single iteration over both the numbers from 1 to n and the target array. Whenever a non-matching number in the stream is encountered (i.e., numbers not in the target), the number is pushed and popped immediately. This results in efficient use of stack operations to match the target.
Time complexity: O(n), Space complexity: O(m), where m is the number of operations.
1
The C solution iterates over the numbers and compares each with the respective target, adding both "Push" and "Pop" operations when a number is not in the target to simulate skipping.