Next Greater Pop Count

Problem

Count the pops performed while finding next greater elements with a monotonic stack. For each index, pop stack indices whose value is strictly smaller than the current value before pushing the current index. Return [pop_count, push_count], where every index is pushed exactly once.

Hint

Each element is pushed once and popped at most once, so the whole scan is O(n).

Test cases

case 1

in: [[2,1,5,3,4]]

expected: [3,5]

case 2

in: [[1,2,3]]

expected: [2,3]

case 3

in: [[3,2,1]]

expected: [0,3]

case 4

in: [[]]

expected: [0,0]

Starter codePython

def next_greater_pop_count(nums):
    # Your code here
    pass

4 test cases · run your code against them in the editor