Coding A Maximum Element In A Stack Hack, Our Attempt

Posted on Oct 5, 2020
The skills I demoed here can be learned through taking Data Science with Machine Learning bootcamp with NYC Data Science Academy.

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

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

Related Articles

Leave a Comment

No comments found.

View Posts by Categories


Our Recent Popular Posts


View Posts by Tags

#python #trainwithnycdsa 2019 2020 Revenue 3-points agriculture air quality airbnb airline alcohol Alex Baransky algorithm alumni Alumni Interview Alumni Reviews Alumni Spotlight alumni story Alumnus ames dataset ames housing dataset apartment rent API Application artist aws bank loans 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 boston safety Bundles cake recipe California Cancer Research capstone car price Career Career Day citibike classic cars classpass clustering Coding Course Demo Course Report covid 19 credit credit card crime frequency crops D3.js data data analysis Data Analyst data analytics data for tripadvisor reviews data science Data Science Academy Data Science Bootcamp Data science jobs Data Science Reviews Data Scientist Data Scientist Jobs data visualization database Deep Learning Demo Day Discount disney dplyr drug data e-commerce economy employee employee burnout employer networking environment feature engineering Finance Financial Data Science fitness studio Flask flight delay gbm Get Hired ggplot2 googleVis Hadoop hallmark holiday movie happiness healthcare frauds higgs boson Hiring hiring partner events Hiring Partners hotels housing housing data housing predictions housing price hy-vee Income Industry Experts Injuries Instructor Blog Instructor Interview insurance italki Job Job Placement Jobs Jon Krohn JP Morgan Chase Kaggle Kickstarter las vegas airport lasso regression Lead Data Scienctist Lead Data Scientist leaflet league linear regression Logistic Regression machine learning Maps market matplotlib Medical Research Meet the team meetup methal health miami beach movie music Napoli NBA netflix Networking neural network Neural networks New Courses NHL nlp NYC NYC Data Science nyc data science academy NYC Open Data nyc property NYCDSA NYCDSA Alumni Online Online Bootcamp Online Training Open Data painter pandas Part-time performance phoenix pollutants Portfolio Development precision measurement prediction Prework Programming public safety PwC python Python Data Analysis python machine learning python scrapy python web scraping python webscraping Python Workshop R R Data Analysis 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 seafood type Selenium sentiment analysis sentiment classification Shiny Shiny Dashboard Spark Special Special Summer Sports statistics streaming Student Interview Student Showcase SVM Switchup Tableau teachers team team performance TensorFlow Testimonial tf-idf Top Data Science Bootcamp Top manufacturing companies Transfers tweets twitter videos visualization wallstreet wallstreetbets web scraping Weekend Course What to expect whiskey whiskeyadvocate wildfire word cloud word2vec XGBoost yelp youtube trending ZORI