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.
1def buildArray(target, n):
2 operations = []
3 t = 0
4 for i in range(1, n + 1):
5 if t == len(target):
6 break
7 operations.append('Push')
8 if i != target[t]:
9 operations.append('Pop')
10 else:
11 t += 1
12 return operations
13
14# Example usage
15result = buildArray([1, 3], 3)
16for op in result:
17 print(op)The Python solution uses a list to collect operations and iterates over numbers from 1 to n while checking against the target array.
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.