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 <stdio.h>
2#include <stdlib.h>
3
4char** buildArray(int* target, int targetSize, int n, int* returnSize) {
5 char **operations = (char **)malloc(200 * sizeof(char*));
6 int t = 0, opIndex = 0;
7 for (int i = 1; i <= n && t < targetSize; ++i) {
8 operations[opIndex++] = "Push";
9 if (i != target[t]) {
10 operations[opIndex++] = "Pop";
11 } else {
12 t++;
13 }
14 }
15 *returnSize = opIndex;
16 return operations;
17}
18
19int main() {
20 int target[] = {1, 3};
21 int targetSize = 2;
22 int n = 3;
23 int returnSize;
24 char** operations = buildArray(target, targetSize, n, &returnSize);
25 for (int i = 0; i < returnSize; i++) {
26 printf("%s\n", operations[i]);
27 }
28 free(operations);
29 return 0;
30}The C solution allocates space for operations and iterates through numbers from 1 to n, keeping track of the current position in the target array. For each number, it determines whether to only push or to push followed by pop based on whether the number is present in the target.
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
Python's solution iterates using a for loop, checking if the current stream number corresponds to the next target number, adding "Push" and "Pop" as necessary.