https://www.acmicpc.net/problem/2493
initial
The logic I tried implementing was simple but I need not make a stack.copy(). It is useless and messes up logic, overconfusing the logic. We don't need to copy and just pop elements in stack with this logic
solution
you unpack a list via the asterisk * operator
from collections import deque
n = int(input())
lst = list(map(int,input().split()))
stack = deque()
ans = [0 for _ in range(n)]
for i in range(len(lst)):
while stack:
if stack[-1][1]>lst[i]:
ans[i]= stack[-1][0] +1
break
else:
stack.pop()
stack.append((i,lst[i]))
print(*ans)complexity
max n^2 time and n space? n^2 cuz u iterate for loop and you can have up to n elements in stack?
No it is just n cuz popping and appending is 0(1) time.
The provided code snippet uses a stack to efficiently find the previous element that is smaller than the current element in the input list. The time complexity of this code is O(n), where n is the number of elements in the input list. Here's the breakdown of the complexity:
-
The main loop iterates through the input list once, so it contributes O(n) to the time complexity.
-
Inside the loop, elements are pushed onto and popped from the stack at most once. Each push and pop operation is an O(1) operation.
Therefore, the overall time complexity of the code is O(n). The space complexity is also O(n) because the stack can contain up to n elements, one for each element in the input list.
