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.
1#include <vector>
2#include <string>
3#include <iostream>
4
5using namespace std;
6
7vector<string> buildArray(vector<int>& target, int n) {
8 vector<string> operations;
9 int t = 0;
10 for (int i = 1; i <= n && t < target.size(); ++i) {
11 operations.push_back("Push");
12 if (i != target[t]) {
13 operations.push_back("Pop");
14 } else {
15 ++t;
16 }
17 }
18 return operations;
19}
20
21int main() {
22 vector<int> target = {1, 3};
23 int n = 3;
24 vector<string> operations = buildArray(target, n);
25 for (const string &op : operations) {
26 cout << op << endl;
27 }
28 return 0;
29}The C++ solution uses a vector of strings to store the operations. It iterates through the numbers while keeping a pointer to the target array to decide whether to perform both push and pop or just a push operation.
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.
1using System.Collections.Generic;
class Program {
static List<string> BuildArray(int[] target, int n) {
List<string> operations = new List<string>();
int targetIndex = 0;
for (int i = 1; i <= n; ++i) {
operations.Add("Push");
if (targetIndex < target.Length && target[targetIndex] == i) {
targetIndex++;
} else {
operations.Add("Pop");
}
}
return operations;
}
static void Main() {
int[] target = {1, 3};
int n = 3;
List<string> operations = BuildArray(target, n);
foreach (string op in operations) {
Console.WriteLine(op);
}
}
}C# uses lists to dynamically manage operations needed to simulate stack building with systematic checks and direct operations.