{"id":2718,"date":"2020-10-06T00:04:27","date_gmt":"2020-10-06T00:04:27","guid":{"rendered":"https:\/\/data-science.gotoauthority.com\/2020\/10\/06\/maximum-element-in-a-stack-hack\/"},"modified":"2020-10-06T00:04:27","modified_gmt":"2020-10-06T00:04:27","slug":"maximum-element-in-a-stack-hack","status":"publish","type":"post","link":"https:\/\/wealthrevelation.com\/data-science\/2020\/10\/06\/maximum-element-in-a-stack-hack\/","title":{"rendered":"Maximum Element In A Stack Hack"},"content":{"rendered":"
\n
\"\"\"\"<\/figure>\n

A Favorite From HackerRank<\/h4>\n

You have an empty sequence, and you will be given N<\/em><\/span> queries. Each query is one of these three types:<\/p>\n

1 x  -Push the element x into the stack.\n2    -Delete the element present at the top of the stack.\n3    -Print the maximum element in the stack.<\/code><\/pre>\n
\n
\n
The first line of input contains an integer, N<\/em><\/span>. The next N<\/em><\/span> lines each contain an above mentioned query. (It is guaranteed that each query is valid.)<\/em><\/p>\n
Constraints<\/strong><\/p>\n
    \n
  • N will always be an integer between 1 and 1e6<\/li>\n
  • x will always be greater than or equal to 1 and less than or equal to 1e10<\/li>\n
  • The type will always be an integer in range (1, 3) inclusive<\/li>\n<\/ul>\n
    \n
    \n
    For each type 3\u00a0<\/span>query, print the maximum element in the stack on a new line.<\/p>\n
    Sample Input<\/strong><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
    10\n1 97\n2\n1 20\n2\n1 26\n1 20\n2\n3\n1 91\n3<\/code><\/pre>\n
    Sample Output<\/strong><\/p>\n
    26\n91<\/code><\/pre>\n
    Our Approach<\/h2>\n
    At first glance this can seem like a challenging task. \u00a0So let’s go through exactly what the question is asking for:<\/p>\n
      \n
    • We have to keep track of the largest element of the sequence<\/li>\n
    • AND THAT’S IT!<\/li>\n<\/ul>\n
      Yup, the only thing we need to do for certain is keep track of the largest element in the list. \u00a0Do we need to keep track of the ordered sequence? No! \u00a0Do we need to return any element other than the largest? No! \u00a0Can we use this to come up with a fast solution? Absolutely!<\/p>\n
      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. \u00a0Therefore, the current largest element will always be at position -1 of our separate list. \u00a0Let’s go through the code to clarify:<\/p>\n
      #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.  \nmax_tracker = [0]\n\n# we cover the entire range of N queries\nfor i in range(int(input())):\n    input_list = list(map(int, input().split()))\n    if input_list[0] == 1:\n      max_tracker.append(max(input_list[1],max_tracker[-1]))\n    elif input_list[0] == 2:\n        max_tracker.pop()\n    else:\n        print(max_tracker[-1])<\/code><\/pre>\n
      Looking at the line:\u00a0max_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. \u00a0However, if the current value is less than our current maximum, then the current maximum is appended to the list again. \u00a0Therefore 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. \u00a0<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
      https:\/\/nycdatascience.com\/blog\/student-works\/maximum-element-in-a-stack\/<\/p>\n","protected":false},"author":0,"featured_media":2719,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts\/2718"}],"collection":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/comments?post=2718"}],"version-history":[{"count":0,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/posts\/2718\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/media\/2719"}],"wp:attachment":[{"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/media?parent=2718"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/categories?post=2718"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wealthrevelation.com\/data-science\/wp-json\/wp\/v2\/tags?post=2718"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}