Online Stock Span

🎯

Online Stock Span

mediumSTACKAmazonGoogle

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.

💡 This problem involves calculating spans of consecutive days with prices not exceeding the current day's price. Beginners often struggle because a naive approach requires checking all previous days repeatedly, leading to inefficiency. Understanding how to use a stack to optimize this process is key.

📋

Problem Statement

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.

💡

Example

Input"next(100), next(80), next(60), next(70), next(60), next(75), next(85)"

Output[1, 1, 1, 2, 1, 4, 6]

For each price, the span is calculated by counting 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.

• Only one price input → span is always 1
• Strictly increasing prices → span equals current day index + 1
• Strictly decreasing prices → span always 1
• All prices equal → span equals current day index + 1

⚠️

Common Mistakes

Not initializing span to 1

Returns 0 span for first day or incorrect spans

✅ Always start span at 1 for the current day

Using a stack that stores only prices without spans or indices

Cannot efficiently calculate spans, leading to incorrect or slow solutions

✅ Store pairs of (price, span) or indices to aggregate spans correctly

Popping from stack while top price is strictly less instead of less or equal

Incorrect spans when prices are equal

✅ Use <= comparison to pop all prices less or equal to current price

Not handling empty stack case when calculating span by index difference

Runtime error or wrong span calculation

✅ Check if stack is empty and handle span as current index + 1

Appending current price before popping smaller prices in brute force

Incorrect span calculation or infinite loops

✅ Append current price after calculating span and popping

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem's core logic by directly implementing the definition, even though it is inefficient. This approach lays the foundation for optimization.

Intuition

For each new price, look backwards day by day until you find a price greater than the current price, counting how many consecutive days have prices less or equal.

Algorithm

1. Initialize an empty list to store all prices seen so far.
2. For each new price, start from the last price and move backwards.
3. Count consecutive days where the price is less than or equal to the current price.
4. Return the count as the span for the current price.

💡 This approach directly follows the problem statement but requires checking all previous prices for each new price, which can be slow.

</>

Code

class StockSpanner:
    def __init__(self):
        self.prices = []

    def next(self, price: int) -> int:
        span = 0
        i = len(self.prices) - 1
        while i >= 0 and self.prices[i] <= price:
            span += 1
            i -= 1
        self.prices.append(price)
        return span + 1

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

Line Notes

self.prices = []Stores all prices seen so far to check previous days when calculating span

span = 0Initialize span count to zero; will count how many previous prices are less or equal

while i >= 0 and self.prices[i] <= price:Iterate backwards over previous prices until a higher price is found

self.prices.append(price)Add current price to the list for future span calculations

return span + 1Add 1 to include the current day in the span

import java.util.*;

class StockSpanner {
    private List<Integer> prices;

    public StockSpanner() {
        prices = new ArrayList<>();
    }

    public int next(int price) {
        int span = 0;
        int i = prices.size() - 1;
        while (i >= 0 && prices.get(i) <= price) {
            span++;
            i--;
        }
        prices.add(price);
        return span + 1;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     StockSpanner spanner = new StockSpanner();
    //     int[] prices = {100, 80, 60, 70, 60, 75, 85};
    //     for (int p : prices) System.out.print(spanner.next(p) + " ");
    // }
}

Line Notes

prices = new ArrayList<>()Stores all prices to check previous days when calculating span

int span = 0;Initialize span count to zero; will count how many previous prices are less or equal

while (i >= 0 && prices.get(i) <= price)Iterate backwards over previous prices until a higher price is found

prices.add(price);Add current price for future span calculations

return span + 1;Add 1 to include the current day in the span

#include <iostream>
#include <vector>
using namespace std;

class StockSpanner {
    vector<int> prices;
public:
    StockSpanner() {}

    int next(int price) {
        int span = 0;
        int i = (int)prices.size() - 1;
        while (i >= 0 && prices[i] <= price) {
            span++;
            i--;
        }
        prices.push_back(price);
        return span + 1;
    }
};

// Example usage:
// int main() {
//     StockSpanner spanner;
//     int prices[] = {100, 80, 60, 70, 60, 75, 85};
//     for (int p : prices) cout << spanner.next(p) << " ";
//     return 0;
// }

Line Notes

vector<int> prices;Stores all prices to check previous days when calculating span

int span = 0;Initialize span count to zero; will count how many previous prices are less or equal

while (i >= 0 && prices[i] <= price)Iterate backwards over previous prices until a higher price is found

prices.push_back(price);Add current price for future span calculations

return span + 1;Add 1 to include the current day in the span

class StockSpanner {
    constructor() {
        this.prices = [];
    }

    next(price) {
        let span = 0;
        let i = this.prices.length - 1;
        while (i >= 0 && this.prices[i] <= price) {
            span++;
            i--;
        }
        this.prices.push(price);
        return span + 1;
    }
}

// Example usage:
// const spanner = new StockSpanner();
// console.log([100, 80, 60, 70, 60, 75, 85].map(p => spanner.next(p)));

Line Notes

this.prices = []Stores all prices to check previous days when calculating span

let span = 0;Initialize span count to zero; will count how many previous prices are less or equal

while (i >= 0 && this.prices[i] <= price)Iterate backwards over previous prices until a higher price is found

this.prices.push(price);Add current price for future span calculations

return span + 1;Add 1 to include the current day in the span

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each price, we may scan all previous prices in worst case, leading to quadratic time. Space is linear to store all prices.

💡 For n=20, this means up to 400 operations, which is manageable, but for n=100000, it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, but it helps understand the problem and motivates optimization.

🧠

Using Monotonic Stack (Stack of Pairs)

💡 This approach uses a stack to keep track of prices and their spans, allowing us to skip multiple previous days at once, drastically improving efficiency.

Intuition

Maintain a stack of pairs (price, span) where prices are in decreasing order. For each new price, pop all prices less or equal to it and accumulate their spans to get the current span.

Algorithm

1. Initialize an empty stack to store pairs of (price, span).
2. For each new price, initialize span as 1.
3. While the stack is not empty and the top price is less or equal to current price, pop it and add its span to current span.
4. Push the current price and its span onto the stack.
5. Return the current span.

💡 This algorithm cleverly skips multiple previous days by aggregating spans, avoiding repeated comparisons.

</>

Code

class StockSpanner:
    def __init__(self):
        self.stack = []  # pair: (price, span)

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

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

Line Notes

self.stack = []Stack stores pairs of (price, span) to aggregate spans efficiently and skip multiple days

span = 1Start span at 1 for the current day as it counts itself

while self.stack and self.stack[-1][0] <= price:Pop all prices less or equal to current price to accumulate their spans

self.stack.append((price, span))Push current price and its total span for future calculations

return spanReturn the calculated span for current price

import java.util.*;

class StockSpanner {
    private Deque<int[]> stack; // stores pairs {price, span}

    public StockSpanner() {
        stack = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     StockSpanner spanner = new StockSpanner();
    //     int[] prices = {100, 80, 60, 70, 60, 75, 85};
    //     for (int p : prices) System.out.print(spanner.next(p) + " ");
    // }
}

Line Notes

stack = new ArrayDeque<>()Stack stores pairs of price and span for efficient aggregation and skipping

int span = 1;Initialize span for current price including itself

while (!stack.isEmpty() && stack.peek()[0] <= price)Pop all smaller or equal prices to accumulate their spans

stack.push(new int[]{price, span});Push current price and its span for future calls

return span;Return the calculated span

#include <iostream>
#include <stack>
using namespace std;

class StockSpanner {
    stack<pair<int,int>> st; // pair: (price, span)
public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

// Example usage:
// int main() {
//     StockSpanner spanner;
//     int prices[] = {100, 80, 60, 70, 60, 75, 85};
//     for (int p : prices) cout << spanner.next(p) << " ";
//     return 0;
// }

Line Notes

stack<pair<int,int>> st;Stack stores pairs of price and span to aggregate spans efficiently and skip multiple days

int span = 1;Start span at 1 for current price including itself

while (!st.empty() && st.top().first <= price)Pop all smaller or equal prices to add their spans

st.push({price, span});Push current price and its span for future queries

return span;Return the calculated span

class StockSpanner {
    constructor() {
        this.stack = []; // stores pairs [price, span]
    }

    next(price) {
        let span = 1;
        while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
            span += this.stack.pop()[1];
        }
        this.stack.push([price, span]);
        return span;
    }
}

// Example usage:
// const spanner = new StockSpanner();
// console.log([100, 80, 60, 70, 60, 75, 85].map(p => spanner.next(p)));

Line Notes

this.stack = []Stack stores pairs of price and span for efficient span calculation and skipping multiple days

let span = 1;Initialize span for current price including itself

while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price)Pop smaller or equal prices to accumulate spans

this.stack.push([price, span]);Push current price and its span for future calls

return span;Return the calculated span

⏱

Complexity

TimeO(n)

SpaceO(n)

Each price is pushed and popped at most once, so total operations are linear. Space stores stack elements up to n.

💡 For n=100000, this means about 200000 operations, which is efficient and feasible.

Interview Verdict: Accepted

This approach is optimal and passes all tests efficiently, making it the preferred solution.

🧠

Design with Precomputed Spans and Index Stack

💡 This approach stores indices instead of spans, computing spans by difference of indices, which can be more intuitive for some and useful for extensions.

Intuition

Use a stack to store indices of days with strictly greater prices. For each new price, pop indices with prices less or equal, then calculate span as difference between current index and top of stack index.

Algorithm

1. Initialize an empty stack to store indices of days with strictly greater prices.
2. For each new price at index i, pop indices from stack while price at those indices is less or equal to current price.
3. If stack is empty, span is i + 1 (all previous days are less or equal).
4. Otherwise, span is difference between current index and top of stack index.
5. Push current index onto stack and return span.

💡 This method uses indices to calculate spans, which can be easier to extend or modify for related problems.

</>

Code

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

    def next(self, price: int) -> int:
        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)
        return span

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

Line Notes

self.stack = []Stack stores indices of days with strictly greater prices to calculate spans by index difference

i = len(self.prices)Current day index, used to calculate span

while self.stack and self.prices[self.stack[-1]] <= price:Pop indices with prices less or equal to current price

span = i + 1 if not self.stack else i - self.stack[-1]Calculate span based on distance to previous higher price index

self.stack.append(i)Push current index for future span calculations

self.prices.append(price)Store current price for comparisons

import java.util.*;

class StockSpanner {
    private Deque<Integer> stack;
    private List<Integer> prices;

    public StockSpanner() {
        stack = new ArrayDeque<>();
        prices = new ArrayList<>();
    }

    public int next(int price) {
        int i = prices.size();
        while (!stack.isEmpty() && prices.get(stack.peek()) <= price) {
            stack.pop();
        }
        int span = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
        prices.add(price);
        return span;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     StockSpanner spanner = new StockSpanner();
    //     int[] prices = {100, 80, 60, 70, 60, 75, 85};
    //     for (int p : prices) System.out.print(spanner.next(p) + " ");
    // }
}

Line Notes

stack = new ArrayDeque<>()Stack stores indices of days with strictly greater prices for span calculation

int i = prices.size();Current day index used to calculate span

while (!stack.isEmpty() && prices.get(stack.peek()) <= price)Pop indices with prices less or equal to current price

int span = stack.isEmpty() ? i + 1 : i - stack.peek();Calculate span by difference of indices

stack.push(i);Push current index for future calculations

prices.add(price);Store current price for comparisons

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

class StockSpanner {
    stack<int> st; // stores indices
    vector<int> prices;
public:
    StockSpanner() {}

    int next(int price) {
        int i = (int)prices.size();
        while (!st.empty() && prices[st.top()] <= price) {
            st.pop();
        }
        int span = st.empty() ? i + 1 : i - st.top();
        st.push(i);
        prices.push_back(price);
        return span;
    }
};

// Example usage:
// int main() {
//     StockSpanner spanner;
//     int prices[] = {100, 80, 60, 70, 60, 75, 85};
//     for (int p : prices) cout << spanner.next(p) << " ";
//     return 0;
// }

Line Notes

stack<int> st;Stack stores indices of days with strictly greater prices for span calculation

int i = (int)prices.size();Current day index used to calculate span

while (!st.empty() && prices[st.top()] <= price)Pop indices with prices less or equal to current price

int span = st.empty() ? i + 1 : i - st.top();Calculate span by difference of indices

st.push(i);Push current index for future calculations

prices.push_back(price);Store current price for comparisons

class StockSpanner {
    constructor() {
        this.stack = []; // stores indices
        this.prices = [];
    }

    next(price) {
        let i = this.prices.length;
        while (this.stack.length > 0 && this.prices[this.stack[this.stack.length - 1]] <= price) {
            this.stack.pop();
        }
        let span = this.stack.length === 0 ? i + 1 : i - this.stack[this.stack.length - 1];
        this.stack.push(i);
        this.prices.push(price);
        return span;
    }
}

// Example usage:
// const spanner = new StockSpanner();
// console.log([100, 80, 60, 70, 60, 75, 85].map(p => spanner.next(p)));

Line Notes

this.stack = []Stack stores indices of days with strictly greater prices for span calculation

let i = this.prices.length;Current day index used to calculate span

while (this.stack.length > 0 && this.prices[this.stack[this.stack.length - 1]] <= price)Pop indices with prices less or equal to current price

let span = this.stack.length === 0 ? i + 1 : i - this.stack[this.stack.length - 1];Calculate span by difference of indices

this.stack.push(i);Push current index for future calculations

this.prices.push(price);Store current price for comparisons

⏱

Complexity

TimeO(n)

SpaceO(n)

Each index is pushed and popped at most once, so total time is linear. Space stores prices and indices up to n.

💡 For large n, this approach is efficient and uses space proportional to input size.

Interview Verdict: Accepted

This approach is also optimal and can be preferred when index-based calculations are needed.

📊

All Approaches - One-Glance Tradeoffs

💡 The monotonic stack approach (Approach 2) is the best to implement in interviews due to its optimal time and space and conceptual clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Monotonic Stack with (price, span)	O(n)	O(n)	No	No (span only)	Code this approach
3. Index Stack with precomputed spans	O(n)	O(n)	No	Yes (can reconstruct days)	Optional alternative to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain inefficiency and motivate stack-based optimization.Step 4: Present the monotonic stack solution with code.Step 5: Discuss time and space complexity and test edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize naive solutions, knowledge of stacks, and coding correctness.

Common Follow-ups

• How to modify if prices can decrease and increase arbitrarily? → The stack approach still works.
• Can you return the actual days included in the span? → Store indices and reconstruct from stack.

💡 These follow-ups test your ability to adapt the solution and extend it beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Need to find spans or counts of consecutive elements meeting a condition 2) Input arrives online or sequentially 3) Problem involves previous elements comparison 4) Efficient skipping of multiple elements is needed

Signature Phrases

maximum number of consecutive daysprice was less than or equalstarting from today and going backwards

NOT This Pattern When

Problems that require global sorting or dynamic programming without monotonic stack usage

Similar Problems

Largest Rectangle in Histogram - uses monotonic stack to find spans of heightsNext Greater Element - uses stack to find next larger element efficiently

Practice

1. You are given an integer array and need to determine if there exists a subsequence of three indices i < j < k such that nums[i] < nums[k] < nums[j]. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force triple nested loops checking all triplets

B. Greedy approach scanning from left to right picking local minima and maxima

C. Using a monotonic stack to track potential '3' and '2' values while iterating backwards

D. Dynamic programming with prefix minimum and suffix maximum arrays

Solution

1. Step 1: Understand the 132 pattern condition

   The problem requires finding a subsequence i < j < k with nums[i] < nums[k] < nums[j], which is the 132 pattern.

2. Step 2: Identify the approach that achieves O(n) time

   The monotonic stack approach iterates from right to left, maintaining candidates for the '3' and '2' elements efficiently, achieving linear time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack approach is known optimal for 132 pattern detection [OK]

Hint: Monotonic stack solves 132 pattern in O(n) [OK]

Common Mistakes:

• Thinking brute force is acceptable for large inputs
• Confusing greedy with monotonic stack
• Assuming DP is needed

2. You need to design a data structure that supports push, pop, top, and retrieving the minimum element in constant time. Which approach guarantees all operations run in O(1) time without scanning the entire stack for the minimum each time?

easy

A. Use a brute force stack and scan the entire stack to find the minimum on each getMin call.

B. Use a dynamic programming table to store minimums for all sub-stacks and update it on each push/pop.

C. Keep two stacks: one for all elements and one for minimum elements, pushing to the min stack only when a new minimum is found.

D. Maintain a single stack that stores the difference between the pushed value and the current minimum, updating the minimum accordingly.

Solution

1. Step 1: Understand the problem constraints

   The goal is to achieve O(1) time for all operations including getMin, without scanning the entire stack.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n), dynamic programming is unnecessary and inefficient, two stacks approach works but uses extra space. The single stack with encoded differences stores relative values and updates min in O(1) time and space efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single stack encoding achieves O(1) time and O(n) space with one stack [OK]

Hint: Single stack encoding stores differences for O(1) min retrieval [OK]

Common Mistakes:

• Thinking scanning stack for min is acceptable
• Confusing two-stack approach as optimal space
• Assuming DP is needed for min tracking

3. Given the following Python function to find previous smaller elements, what is the output when the input array is [3, 7, 1]?

def previous_smaller_element_indexes(arr):
    stack = []
    result = []
    for i, num in enumerate(arr):
        while stack and arr[stack[-1]] >= num:
            stack.pop()
        if stack:
            result.append(arr[stack[-1]])
        else:
            result.append(-1)
        stack.append(i)
    return result

print(previous_smaller_element_indexes([3, 7, 1]))

easy

A. [-1, -1, -1]

B. [-1, 3, -1]

C. [-1, 3, 3]

D. [3, -1, -1]

Solution

1. Step 1: Trace iteration i=0, num=3

   Stack empty, append -1 to result, push index 0 -> stack=[0], result=[-1]

2. Step 2: Trace iteration i=1, num=7

   Stack top index 0 -> arr[0]=3 < 7, so append 3 to result, push index 1 -> stack=[0,1], result=[-1,3]

3. Step 3: Trace iteration i=2, num=1

   Pop while arr[stack[-1]] >= 1: arr[1]=7 >=1 pop, arr[0]=3 >=1 pop, stack empty, append -1, push index 2 -> stack=[2], result=[-1,3,-1]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Output matches expected previous smaller elements for each position [OK]

Hint: Pop all >= current to find closest smaller on left [OK]

Common Mistakes:

• Not popping equal or greater elements leads to wrong result
• Appending wrong element from stack top
• Off-by-one errors in indexing

4. Suppose the problem is modified so that the array is circular and you want to find the next greater element allowing repeated reuse of elements (i.e., you can wrap around multiple times). Which modification to the monotonic stack approach correctly handles this variant?

hard

A. Modify the stack to store values instead of indices to handle repeated reuse

B. Use a brute force nested loop with modulo indexing to simulate infinite wrap

C. Extend the doubled array to triple or more copies and run the same monotonic stack algorithm

D. Use a queue instead of a stack to process elements in order for multiple wraps

Solution

1. Step 1: Understand problem variant

   Allowing repeated reuse means next greater element might appear after multiple wraps, not just one.

2. Step 2: Modify approach accordingly

   Extending the array to triple or more copies simulates multiple wraps, allowing monotonic stack to find next greater elements beyond one wrap.

3. Step 3: Why other options fail

   Brute force is inefficient; storing values loses index mapping; queue does not maintain monotonic property needed.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Extending array copies simulates multiple wraps correctly [OK]

Hint: Multiple wraps -> extend array copies accordingly [OK]

Common Mistakes:

• Using brute force which is inefficient
• Storing values instead of indices losing position info
• Replacing stack with queue losing monotonic property

5. 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