Maximum Element In A Stack Hack

Daniel Brancusi
Posted on Oct 5, 2020

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
3

Sample Output

26
91

Our 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!

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

Related Articles

Leave a Comment

No comments found.

View Posts by Categories


Our Recent Popular Posts


View Posts by Tags

#python #trainwithnycdsa 2019 airbnb Alex Baransky alumni Alumni Interview Alumni Reviews Alumni Spotlight alumni story Alumnus API Application artist aws beautiful soup Best Bootcamp Best Data Science 2019 Best Data Science Bootcamp Best Data Science Bootcamp 2020 Best Ranked Big Data Book Launch Book-Signing bootcamp Bootcamp Alumni Bootcamp Prep Bundles California Cancer Research capstone Career Career Day citibike clustering Coding Course Demo Course Report D3.js data Data Analyst data science Data Science Academy Data Science Bootcamp Data science jobs Data Science Reviews Data Scientist Data Scientist Jobs data visualization Deep Learning Demo Day Discount dplyr employer networking feature engineering Finance Financial Data Science Flask gbm Get Hired ggplot2 googleVis Hadoop higgs boson Hiring hiring partner events Hiring Partners Industry Experts Instructor Blog Instructor Interview Job Job Placement Jobs Jon Krohn JP Morgan Chase Kaggle Kickstarter lasso regression Lead Data Scienctist Lead Data Scientist leaflet linear regression Logistic Regression machine learning Maps matplotlib Medical Research Meet the team meetup Networking neural network Neural networks New Courses nlp NYC NYC Data Science nyc data science academy NYC Open Data NYCDSA NYCDSA Alumni Online Online Bootcamp Online Training Open Data painter pandas Part-time Portfolio Development prediction Prework Programming PwC python python machine learning python scrapy python web scraping python webscraping Python Workshop R R language R Programming R Shiny r studio R Visualization R Workshop R-bloggers random forest Ranking recommendation recommendation system regression Remote remote data science bootcamp Scrapy scrapy visualization seaborn Selenium sentiment analysis Shiny Shiny Dashboard Spark Special Special Summer Sports statistics streaming Student Interview Student Showcase SVM Switchup Tableau team TensorFlow Testimonial tf-idf Top Data Science Bootcamp twitter visualization web scraping Weekend Course What to expect word cloud word2vec XGBoost yelp