3
\$\begingroup\$

I've tried asking about the performance on the HackerRank discussion forum, it didn't work out.

The task is to write a program with three operations:

 1 x  Push the element x onto the stack.    
 2    Delete the element present at the top of the stack.   
 3    Print the maximum element in the stack.

The first input line is the number of lines in the program, all subsequent lines are one of the three instructions.

Sample Input:

 10
 1 97
 2
 1 20
 2
 1 26
 1 20
 2
 3
 1 91
 3

Sample Output:

 26
 91

My Solution:

data = []
for _ in range(int(input())):
    ins = input().split()
    if ins[0] == '1':
        data.append(int(ins[1]))
    elif ins[0] == '2':
        data.pop()
    else:
        print(max(data))

It gets slow on working with input size of 1000 elements or so, how could I speed this up?

\$\endgroup\$
  • 3
    \$\begingroup\$ You should keep track of the maximum, because using max(data) needs to go through the whole list. \$\endgroup\$ – Quentin Pradet Sep 16 '16 at 10:09
  • 1
    \$\begingroup\$ You should also think of a better title. A title that describes what your code does and not what you want out of a review attracts a lot more views and consequentially also more answers. \$\endgroup\$ – Graipher Sep 16 '16 at 10:47
  • \$\begingroup\$ @Graipher Thanks for that It looks much better now \$\endgroup\$ – Jøê Grèéñ Sep 16 '16 at 10:59
3
\$\begingroup\$

Try tracking the current maximum, otherwise frequent occurrences of 3 will push your run time towards \$\mathcal{O}(n^2)\$.

If you take a closer look at what your input actually means, you will notice that smaller values being pushed onto the stack have actually no significance if a greater value has being pushed previously. So for every fill level of the stack, you already know the corresponding maximum at the time you push onto the stack.

Use that knowledge:

current_max = []
for _ in range(int(input())):
    ins = input().split()
    if ins[0] == '1':
        new_max = int(ins[1])
        if current_max and new_max < current_max[-1]:
            new_max = current_max[-1]
        current_max.append(new_max)
    elif ins[0] == '2':
        current_max.pop()
    elif ins[0] == '3':
        print(current_max[-1])

By storing the maximum instead of the raw value on the stack, you can always access the current maximum directly. Just don't forget to handle the special case when data is empty, so the new value will always be the maximum.

\$\endgroup\$
  • \$\begingroup\$ I agree, the max is probably what is killing the time for large lists. However, there should also be a handling in the pop part, because you might pop off the maximum value. \$\endgroup\$ – Graipher Sep 16 '16 at 11:05
  • \$\begingroup\$ No popping the max value is allowed please see the sample input and sample out @Graipher \$\endgroup\$ – Jøê Grèéñ Sep 16 '16 at 11:07
  • 1
    \$\begingroup\$ @JøêGrèéñ Well, this is something you should explicitly state! Just because it does not happen in your one example does not mean it is not going to happen. The defined instructions would allow for it (and do not say what happens if you try to pop the maximum value). \$\endgroup\$ – Graipher Sep 16 '16 at 11:08
  • 2
    \$\begingroup\$ @Graipher Even when the former maximum is popped - the top of data still holds the next valid maximum, which is always <= the former maximum. \$\endgroup\$ – Ext3h Sep 16 '16 at 11:33
  • 1
    \$\begingroup\$ @JøêGrèéñ The size of the stack needs to correspond with the number of push operations specified by the input. If the data is smaller than the current maximum, you still need to push something onto the stack. The safest value for that is simply copying the current maximum instead, since the data you just received can never be maximum anyway. \$\endgroup\$ – Ext3h Sep 16 '16 at 11:37
3
\$\begingroup\$

One remark. A stack is not a set, you could have the maximal value happening twice. And deletes may happen too.

This in fact means you need a running maximum.

Hence create a stack of a pair (value, max till now).

The implementation then is quite simple for all three operations.......

\$\endgroup\$
  • 2
    \$\begingroup\$ I havn't used a set sir \$\endgroup\$ – Jøê Grèéñ Sep 16 '16 at 11:02
  • 1
    \$\begingroup\$ I meant a mathematical set, where all values are unique. The first answer is fine, but ticklish. Because deleting a prior max value can find the same max value if that value was pushed twice. Hence my proposal. \$\endgroup\$ – Joop Eggen Sep 16 '16 at 11:08
  • \$\begingroup\$ @JoeWallis it was intended as a warning that a stack can have several max values. So deleting a max value does not automatically give a smaller max value, and adding the same max value needs needs to duplicate that max value. Must express myself more clear, thanks. \$\endgroup\$ – Joop Eggen Sep 16 '16 at 11:25
  • \$\begingroup\$ The actual value is completely irrelevant for this problem. Just recording "max till now" is completely sufficient. Which is exactly what the accepted answer does. \$\endgroup\$ – Ext3h Sep 16 '16 at 11:31
  • \$\begingroup\$ @JoopEggen I failed to understand the bolded part of your answer as I was fixated on the set part. I noticed after posting my comment and so deleted it, in the hopes you'd not have seen it. Your reasoning is definitely clear in your comment. \$\endgroup\$ – Peilonrayz Sep 16 '16 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.