Interview Prepstacks-monotonic-stackmediumAmazonGoogle

Online Stock Span

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine you're a stock trader who wants to quickly know how many consecutive days the stock price has been less than or equal to today's price, to gauge momentum.

Design a class StockSpanner that collects daily stock prices and returns the span of the stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. Implement the StockSpanner class: - StockSpanner() Initializes the object of the class. - int next(int price) Returns the span of the stock's price given that today's price is price.

1 ≤ price ≤ 10^5At most 10^5 calls will be made to next.

Edge cases: Only one price input → span is always 1Strictly increasing prices → span equals current day index + 1Strictly decreasing prices → span always 1

</>

IDE

def next(self, price: int) -> int:

class StockSpanner:
    def __init__(self):
        # Write your solution here
        pass
    
    def next(self, price: int) -> int:
        pass

class StockSpanner {
    public StockSpanner() {
        // Write your solution here
    }
    public int next(int price) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

class StockSpanner {
public:
    StockSpanner() {
        // Write your solution here
    }
    int next(int price) {
        // Write your solution here
        return 0;
    }
};

class StockSpanner {
    constructor() {
        // Write your solution here
    }
    next(price) {
        // Write your solution here
    }
}

0/9

Common Bugs to Avoid

Wrong: [1, 1, 1, 1, 1, 1, 1]Not popping previous prices less or equal to current price, always returning 1.✅ Pop from stack while top price <= current price and sum their spans before pushing current price.

Wrong: [1, 2, 3, 4, 1]Incorrectly resetting span after a local decrease instead of continuing to pop all smaller or equal prices.✅ Ensure popping continues while top price <= current price, not just immediate previous price.

Wrong: [1, 1, 1, 2, 1, 1, 1]Not accumulating spans from popped elements, only counting current price as span 1.✅ Accumulate spans from all popped elements and add 1 for current price before pushing.

Wrong: TLE or timeoutUsing brute force nested loops scanning all previous prices for each next call.✅ Implement monotonic stack to achieve O(n) time complexity by pushing and popping prices once.

✓

Test Cases

t1_01basic

Input{"calls":["next(100)","next(80)","next(60)","next(70)","next(60)","next(75)","next(85)"]}

Expected[1,1,1,2,1,4,6]

For each price, the span counts consecutive previous days with price less or equal to current price. For example, for price 75, previous prices 60, 70, 60 are less or equal, so span is 4.

t1_02basic

Input{"calls":["next(31)","next(41)","next(48)","next(59)","next(79)"]}

Expected[1,2,3,4,5]

Strictly increasing prices cause spans to increase by 1 each day, so spans are [1,2,3,4,5].

Practice

(1/5)

1. Consider the following Python code implementing the optimal 132 pattern detection algorithm. What is the return value when the input is [3, 1, 4, 2]?

easy

A. None

B. False

C. Raises an error

D. True

2. Consider the following Python code that evaluates Reverse Polish Notation expressions. What is the final output when the input tokens are ["4", "13", "5", "/", "+"]?

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

sol = Solution()
print(sol.evalRPN(["4", "13", "5", "/", "+"]))

easy

A. 2

B. 6

C. 8

D. 10

5. The following code attempts to solve the Next Greater Element II problem using a monotonic stack and explicit circular array copy. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    doubled = nums + nums
    answer = [-1] * n
    stack = []
    for i, num in enumerate(doubled):
        while stack and doubled[stack[-1]] < num:
            idx = stack.pop()
            if idx < n:
                answer[idx] = num
        if i < n:
            stack.append(i)  # Bug here
    return answer

medium

A. Line pushing indices onto stack only when i < n

B. Line popping from stack while top element is less than current num

C. Line initializing answer array with -1

D. Line creating doubled array by concatenation

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Online Stock Span

Practice

Solution

Step 1: Trace the loop with input [3,1,4,2]

Step 2: Confirm early return

Final Answer:

Quick Check:

Solution

Step 1: Trace stack operations

Step 2: Final stack pop

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify the approach that finds boundaries in O(n)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Understand stack push condition

Step 2: Identify correct push strategy

Final Answer:

Quick Check:

Ready to prove it?