FastPrepMax Stack
Problem · Stack

Max Stack

Learn this problem
● HardLinkedIn logoLinkedInFULLTIMEONSITE INTERVIEW

Problem statement

Implement a max stack by processing the finite array operations from left to right. The stack starts empty.

Each operation has one of these forms:

  • PUSH value: push value onto the top of the stack.
  • POP: remove and return the top value.
  • PEEK: return the top value without removing it.
  • PEEK_MAX: return the largest value currently in the stack without removing it.
  • POP_MAX: remove and return the largest value. If the maximum occurs more than once, remove the occurrence closest to the top.

Return the values produced by every operation except PUSH, in command order.

Function

runMaxStack(operations: String[]) → int[]

Examples

Example 1

operations = ["PUSH 5","PUSH 1","PUSH 5","PEEK","POP_MAX","PEEK","PEEK_MAX","POP","PEEK"]return = [5,5,1,5,1,5]

POP_MAX removes the upper copy of 5. The stack is then [5,1] from bottom to top.

Example 2

operations = ["PUSH 2","PUSH 2","PUSH 1","POP_MAX","PEEK","POP","PEEK_MAX"]return = [2,1,1,2]

The topmost maximum is the second pushed 2, even though 1 is above it. Removing that node leaves 1 on top.

Constraints

  • 1 <= operations.length <= 100000.
  • Every operation is exactly one documented command; PUSH has one separating space before its value.
  • -10^9 <= value <= 10^9.
  • Every POP, PEEK, PEEK_MAX, and POP_MAX is issued while the stack is nonempty.
  • At least one operation produces output.

More LinkedIn problems

drafts saved locally
public int[] runMaxStack(String[] operations) {
    // Write your code here.
}
operations["PUSH 5","PUSH 1","PUSH 5","PEEK","POP_MAX","PEEK","PEEK_MAX","POP","PEEK"]
expected[5,5,1,5,1,5]
checking account