Online Stock Span

▶

Steps

setup

Initialize / Setup

Initialize an empty stack and an empty prices list to start processing stock prices.

💡 This setup is crucial because the stack will hold indices of days, and prices will store the actual stock prices for comparison.

Line:

self.stack = []  # stores indices
self.prices = []

💡 The algorithm uses two data structures: one for prices and one for indices to efficiently compute spans.

insert

Process price 100 at index 0

Process the first price 100 at index 0. Since the stack is empty, no popping occurs.

💡 With no previous prices, the span is simply 1 (the current day itself).

Line:

i = len(self.prices)
while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()
span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 An empty stack means all previous prices are less or equal, so span covers all days up to current.

insert

Process price 80 at index 1

Process price 80 at index 1. The top of the stack is index 0 with price 100, which is greater than 80, so no popping.

💡 Since the top price is greater, the span is the difference between current index and top index.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()
span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 The stack top acts as a boundary limiting the span to days after that index.

insert

Process price 60 at index 2

Process price 60 at index 2. The top of the stack is index 1 with price 80, which is greater than 60, so no popping.

💡 Span is again the difference between current index and top index on the stack.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()
span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 Stack top index continues to limit the span to recent higher price day.

delete

Process price 70 at index 3 - Pop smaller or equal prices

Process price 70 at index 3. Pop indices while top price ≤ 70. Pop index 2 (price 60) because 60 ≤ 70.

💡 Popping removes days with prices not greater than current, extending the span.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()

💡 Popping smaller or equal prices allows the span to cover more days.

insert

Calculate span and push index for price 70 at index 3

After popping, top of stack is index 1 with price 80 > 70, so span = 3 - 1 = 2. Push current index 3.

💡 Span is distance from last higher price day to current day.

Line:

span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 Span calculation depends on the nearest previous day with a higher price.

insert

Process price 60 at index 4

Process price 60 at index 4. Top of stack is index 3 with price 70 > 60, no popping.

💡 Span is difference between current index and top index.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()
span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 Stack top index limits span to recent higher price day.

delete

Process price 75 at index 5 - Pop smaller or equal prices

Process price 75 at index 5. Pop indices while top price ≤ 75: pop index 4 (60), pop index 3 (70).

💡 Popping smaller or equal prices extends the span backwards.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()

💡 Removing these indices allows the span to cover more days.

insert

Calculate span and push index for price 75 at index 5

After popping, top of stack is index 1 with price 80 > 75, so span = 5 - 1 = 4. Push current index 5.

💡 Span is distance from last higher price day to current day.

Line:

span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 Span calculation depends on nearest previous day with higher price.

delete

Process price 85 at index 6 - Pop smaller or equal prices

Process price 85 at index 6. Pop indices while top price ≤ 85: pop index 5 (75), pop index 1 (80).

💡 Popping these indices extends the span to cover more previous days.

Line:

while self.stack and self.prices[self.stack[-1]] <= price:
    self.stack.pop()

💡 Popping removes all days with prices not strictly greater than current price.

insert

Calculate span and push index for price 85 at index 6

After popping, top of stack is index 0 with price 100 > 85, so span = 6 - 0 = 6. Push current index 6.

💡 Span is distance from last higher price day to current day.

Line:

span = i + 1 if not self.stack else i - self.stack[-1]
self.stack.append(i)
self.prices.append(price)

💡 Final span calculation uses the nearest previous day with higher price.

reconstruct

Final state after processing all prices

All prices processed. The final stack contains indices of days with strictly greater prices. The output spans are [1, 1, 1, 2, 1, 4, 6].

💡 The final stack state confirms the monotonic property and the correctness of span calculations.

💡 The stack efficiently encodes the boundaries for span calculations.

class StockSpanner:
    def __init__(self):
        self.stack = []  # stores indices  # STEP 1
        self.prices = []

    def next(self, price: int) -> int:
        i = len(self.prices)  # current index  # STEP 2
        while self.stack and self.prices[self.stack[-1]] <= price:  # STEP 5,8,10
            self.stack.pop()  # pop smaller or equal prices
        span = i + 1 if not self.stack else i - self.stack[-1]  # STEP 3,4,6,9,11
        self.stack.append(i)  # push current index
        self.prices.append(price)
        return span

# Example usage:
# spanner = StockSpanner()
# print([spanner.next(p) for p in [100, 80, 60, 70, 60, 75, 85]])

📊

Online Stock Span - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation on the stack reveals how the algorithm skips over previous days with lower prices, making the span calculation efficient and intuitive.

no_op

Stack (top→bottom)

empty

pushElement[0]: 100

Stack (top→bottom)

0

↑ pushed: 0

Contributes: 1

pushElement[1]: 80

Stack (top→bottom)

1

0

↑ pushed: 1

Contributes: 1

pushElement[2]: 60

Stack (top→bottom)

2

1

0

↑ pushed: 2

Contributes: 1

popElement[3]: 70

Stack (top→bottom)

1

0

↓ popped: [2]

pushElement[3]: 70

Stack (top→bottom)

3

1

0

↑ pushed: 3

Contributes: 2

pushElement[4]: 60

Stack (top→bottom)

4

3

1

0

↑ pushed: 4

Contributes: 1

popElement[5]: 75

Stack (top→bottom)

1

0

↓ popped: [4, 3]

pushElement[5]: 75

Stack (top→bottom)

5

1

0

↑ pushed: 5

Contributes: 4

popElement[6]: 85

Stack (top→bottom)

0

↓ popped: [5, 1]

pushElement[6]: 85

Stack (top→bottom)

6

0

↑ pushed: 6

Contributes: 6

no_opElement[6]: 85

Stack (top→bottom)

6

0

Key Takeaways

✓ The stack maintains indices of days with strictly greater prices, enabling efficient span calculation by skipping over smaller or equal prices.

This insight is hard to see from code alone because the stack operations abstract away the repeated comparisons.

✓ Popping from the stack removes all previous days that do not limit the span, effectively compressing the search space for the span calculation.

Visualizing the popping clarifies how the algorithm avoids scanning all previous days for each price.

✓ The span for each day is either the entire range from day 0 if the stack is empty or the difference between current day and the nearest previous day with a higher price.

Seeing the stack top index used to compute span concretely connects the data structure to the output.

Practice

1. Given the following code snippet for decoding strings, what is the final returned string when the input is 2[ab]?

easy

A. abab

B. ab2

C. 2ab

D. aabb

Solution

1. Step 1: Trace parsing of '2[ab]'

   k accumulates 2, '[' pushes k=2 and empty string stack, current_string resets, then 'a','b' appended.

2. Step 2: On ']', pop count=2 and prev_string=[], current_string becomes [] + ['a','b']*2 = ['a','b','a','b']

   Return joined string 'abab'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected repeated substring 'abab' [OK]

Hint: Repeat count multiplies substring inside brackets [OK]

Common Mistakes:

• Misinterpreting repeat count as string
• Appending digits as characters

2. Suppose the input stream can contain uppercase and lowercase letters (52 possible characters) instead of only lowercase. Which modification to the optimal solution is correct to handle this variant efficiently?

hard

A. Use a frequency map (dictionary) instead of fixed-size array and keep the queue logic unchanged.

B. Keep the fixed-size frequency array of length 26 and convert uppercase to lowercase before processing.

C. Use two separate frequency arrays for uppercase and lowercase letters and merge results after processing.

D. Use a brute force scan of the entire stream each time since fixed-size arrays no longer apply.

Solution

1. Step 1: Recognize input change

   Input now has 52 characters, so fixed-size array of length 26 is insufficient.

2. Step 2: Choose data structure

   A frequency map (dictionary) can handle arbitrary characters efficiently with O(1) average access.

3. Step 3: Keep queue logic

   The queue logic remains the same, tracking candidates for first unique character.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dictionary replaces fixed array for larger character set [OK]

Hint: Use dictionary for frequency when character set is larger [OK]

Common Mistakes:

• Trying to map uppercase to lowercase losing case info
• Using two arrays complicates logic unnecessarily
• Reverting to brute force loses efficiency

3. Suppose the input array can contain negative numbers and duplicates, and you want to find the previous smaller element for each position. Which modification to the monotonic stack algorithm is necessary to handle duplicates correctly and maintain O(n) time?

hard

A. Change the popping condition to pop elements strictly greater than current (arr[stack[-1]] > num)

B. Store values instead of indexes in the stack to simplify comparisons

C. Use a balanced binary search tree instead of a stack to handle duplicates

D. Change the popping condition to pop elements greater than or equal to current (arr[stack[-1]] >= num)

Solution

1. Step 1: Understand the role of popping condition

   To correctly handle duplicates, the stack must pop elements that are greater than or equal to the current element to maintain strictly increasing order.

2. Step 2: Evaluate options for duplicates and negative numbers

   Using '>=' ensures duplicates are popped, preventing incorrect previous smaller elements; other options either break correctness or efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pop equal or greater elements to maintain correct monotonic stack with duplicates [OK]

Hint: Pop >= current to handle duplicates correctly [OK]

Common Mistakes:

• Using '>' only causes duplicates to remain on stack
• Replacing stack with BST increases complexity unnecessarily
• Pushing values instead of indexes loses position info

4. Suppose the sliding window maximum problem is modified so that the window size k can vary dynamically during the iteration. Which of the following approaches correctly adapts the monotonic deque solution to handle this efficiently?

hard

A. Adjust the window boundary checks and remove indices outside the current window size dynamically without rebuilding the deque

B. Rebuild the deque from scratch each time the window size changes

C. Switch to a max heap data structure since deque cannot handle variable window sizes

D. Use a brute force approach for variable window sizes to avoid complexity

Solution

1. Step 1: Understand dynamic window size impact

   Window boundaries change, so indices outside the current window must be removed accordingly.

2. Step 2: Adapt monotonic deque maintenance

   Instead of rebuilding, update boundary checks and pop indices outside the new window size dynamically.

3. Step 3: Evaluate alternatives

   Rebuilding deque or switching to heap is inefficient; brute force is too slow.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dynamic boundary checks maintain O(n) amortized complexity [OK]

Hint: Update boundary removals dynamically, avoid rebuilding [OK]

Common Mistakes:

• Rebuilding deque wastes time
• Assuming heap is better for variable k

5. Suppose the problem changes so that elements in the array can be negative integers. Which modification to the monotonic stack approach is necessary to correctly compute the sum of subarray minimums?

hard

A. Add a sentinel element with value 0 at the end to ensure stack empties correctly

B. No change needed; the existing monotonic stack approach works for negative values

C. Use a different data structure like a balanced BST to handle negative values

D. Modify the comparison to use <= instead of < to handle negative duplicates

Solution

1. Step 1: Analyze effect of negative values on monotonic stack

   The monotonic stack approach relies on relative ordering, which holds regardless of sign.

2. Step 2: Confirm no structural changes needed

   Sentinel and strict < comparison still work; negative values do not break the logic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack handles negatives without modification [OK]

Hint: Monotonic stack compares values, sign does not affect correctness [OK]

Common Mistakes:

• Assuming negative values require different data structures
• Changing comparison operators unnecessarily