Coding A Maximum Element In A Stack Hack, Our Attempt
The skills I demoed here can be learned through taking Data Science with Machine Learning bootcamp with NYC Data Science Academy.
LinkedIn | GitHub | Email | Data | Web App
A Favorite From HackerRank
You have an empty sequence, and you will be given N queries. Each query is one of these three types:
1 x -Push the element x into the stack.
2 -Delete the element present at the top of the stack.
3 -Print the maximum element in the stack.Input Format
The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)
Constraints
- N will always be an integer between 1 and 1e6
- x will always be greater than or equal to 1 and less than or equal to 1e10
- The type will always be an integer in range (1, 3) inclusive
Output Format
For each type 3 query, print the maximum element in the stack on a new line.
Sample Input
10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3Sample Output
26
91Our Approach
At first glance this can seem like a challenging task. So let's go through exactly what the question is asking for:
- We have to keep track of the largest element of the sequence
- AND THAT'S IT!
Yup, the only thing we need to do for certain is keep track of the largest element in the list. Do we need to keep track of the ordered sequence? No! Do we need to return any element other than the largest? No! Can we use this to come up with a fast solution? Absolutely!
Solution
The trick that we are going to employ revolves around keeping track of the largest element in a separate list and only appending items to that list which are either larger than the current largest element or we will append the current largest element to the list again. Therefore, the current largest element will always be at position -1 of our separate list. Let's go through the code to clarify:
#set initial value of our maximum element tracking at 0 so #that any value passed via input will exceed this value and #become the subsequent maximum.
max_tracker = [0]
# we cover the entire range of N queries
for i in range(int(input())):
input_list = list(map(int, input().split()))
if input_list[0] == 1:
max_tracker.append(max(input_list[1],max_tracker[-1]))
elif input_list[0] == 2:
max_tracker.pop()
else:
print(max_tracker[-1])Looking at the line: max_tracker.append( max ( input_list[1], max_tracker[-1] ) ) we see that if the current value is larger than our previous maximum then the current value is appended to the list. However, if the current value is less than our current maximum, then the current maximum is appended to the list again. Therefore we always have the maximum element in the [-1] position and we can simply pop the last element if we need to remove the element present at the top of the stack while not disrupting the order needed to solve the question.
About Author
