Recognize amortized O(n) pop-while
Updated
A single pop-while can pop k items (O(k) that call), but each item is pushed once and popped at most once across the whole scan, so the scan is O(n) amortized. Nested for-loops that rescan left are O(n²).
What to focus on
The stack is why next-greater is linear. If you search right for each i independently, you lose the amortization. Count total pops ≤ n.
Worked examples
one expensive call
a = [1, 2, 3, 10], last 10 pops three- this call O(3)
- those 1,2,3 never pop again
Result: amortized O(1) per item
whole scan
a = [1, 2, 3, 10]- 4 pushes, 3 pops, 1 leftover
Result: O(n)
naive nested
a = [1, 2, 3, 10], for each i scan j>i- about n²/2 compares
Result: O(n²)
Try it
Write countOps(a). a is an array of integers. Count total pushes and pops in the stack next-greater scan versus nested search. One pop-while may be O(n). The algorithm is still O(n). a = [1, 2, 3, 10], last 10 pops three → amortized O(1) per item. a = [1, 2, 3, 10] → O(n). a = [1, 2, 3, 10], for each i scan j>i → O(n²).
a is a non-empty list of integers. Count total stack ops across the whole scan.