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.
1using System;
2using System.Collections.Generic;
3
4class Program {
5 static List<string> BuildArray(int[] target, int n) {
6 List<string> operations = new List<string>();
7 int t = 0;
8 for (int i = 1; i <= n && t < target.Length; ++i) {
9 operations.Add("Push");
10 if (i != target[t]) {
11 operations.Add("Pop");
12 } else {
13 ++t;
14 }
15 }
16 return operations;
17 }
18
19 static void Main() {
20 int[] target = {1, 3};
21 int n = 3;
22 List<string> operations = BuildArray(target, n);
23 foreach (string op in operations) {
24 Console.WriteLine(op);
25 }
26 }
27}This C# solution makes use of a List to manage the operations. It compares each number in sequence from 1 to n against the target list, adding 'Push' for each, and 'Pop' if there is no match.
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.