901.online-stock-span.md

901. Online Stock Span

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

We store the price and how many days that prices is less than the current price (the span) into stack. So that we will know the total days before that price is less than or equal to the current price.

Price = 60
Stack: [60,1]

Price = 70
// We pop [60,1] and update the span for 70
Stack: [70,1+1]

Price = 60
Stack: [70,2] / [60,1]

Price = 75
// Pop [60,1] / [70,2]
Stack: [75, 1+1+2]
// First 1 for 75, second 1 from [60,1], 2 from [70,2]

// Monotonic decreasing stack
private val stack = Stack<IntArray>()

fun next(price: Int): Int {
    var answer = 1
    while (stack.isNotEmpty() && stack.peek()[0] <= price) {
        val array = stack.pop()
        val span = array[1]
        answer += span
    }
    stack.push(intArrayOf(price, answer))
    return answer
}

• Time Complexity: One price will be pushed once and popped once. So 2n times stack operations and n times calls, time complexity is amortized O(1)
• Space Complexity: O(n) for stack.