What is the time complexity of Online Stock Span?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Online Stock Span?

This problem uses Stack, Design, Monotonic Stack, Data Stream. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Online Stock Span?

Insight 1: The key insight is that we need to efficiently find the number of consecutive days before the current day where the price was less than or equal to the current day's price. Insight 2: A stack is the appropriate data structure to maintain a decreasing sequence of prices and their spans encountered so far. This allows us to quickly determine the span for the current day.

Which companies ask LeetCode 901. Online Stock Span in interviews?

This problem is frequently asked at INDmoney.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Online Stock Span - LeetCode 901 Solution

Online Stock Span - Complete Solution Guide

Online Stock Span is LeetCode problem 901, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day. For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2 , then the span of today is 4 because starting from t

Detailed Explanation

The problem asks us to design a `StockSpanner` class that calculates the 'span' of a stock's price for each day. The span for a given day is defined as the maximum number of consecutive days (including the current day and going backward) where the stock price was less than or equal to the current day's price. We need to implement a `next(int price)` method that takes the current day's price as input and returns its span.

Solution Approach

The solution uses a stack to maintain a decreasing sequence of prices along with their spans. When a new price comes in, we iterate through the stack and pop all the elements whose prices are less than or equal to the current price. As we pop these elements, we accumulate their spans. Finally, we push the current price and its calculated span onto the stack.

Step-by-Step Algorithm

Step 1: Initialize an empty stack. Each element in the stack will be a pair (price, span).
Step 2: When the `next(price)` method is called, initialize a variable `span` to 1 (the span for the current day itself).
Step 3: While the stack is not empty and the price at the top of the stack is less than or equal to the current `price`, pop the element from the stack and add its span to the current `span`.
Step 4: After popping all the necessary elements, push the current `price` and its calculated `span` onto the stack.
Step 5: Return the calculated `span`.

Key Insights

Insight 1: The key insight is that we need to efficiently find the number of consecutive days before the current day where the price was less than or equal to the current day's price.
Insight 2: A stack is the appropriate data structure to maintain a decreasing sequence of prices and their spans encountered so far. This allows us to quickly determine the span for the current day.
Insight 3: The stack stores pairs of (price, span) for previous days. When a new price comes in, we pop elements from the stack whose price is less than or equal to the current price. The span of the current price is then the sum of the spans of the popped elements plus 1 (for the current day).

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Stack, Design, Monotonic Stack, Data Stream.

Companies

Asked at: INDmoney.

Online Stock Span | LeetCode 901

Medium

Stack Design Monotonic Stack Data Stream

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.Stack;

class StockSpanner {

    private Stack<int[]> stack;

    public StockSpanner() {
        this.stack = new Stack<>();
    }

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

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 901: Online Stock Span - Detailed explanation and solution approaches.

Topics

Stack Design Monotonic Stack Data Stream

Companies

INDmoney

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:901

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize an empty stack. Each element in the stack will be a pair (price, span).
2
Step 2: When the `next(price)` method is called, initialize a variable `span` to 1 (the span for the current day itself).
3
Step 3: While the stack is not empty and the price at the top of the stack is less than or equal to the current `price`, pop the element from the stack and add its span to the current `span`.
4
Step 4: After popping all the necessary elements, push the current `price` and its calculated `span` onto the stack.
5
Step 5: Return the calculated `span`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is amortized O(n) because, though some `next()` calls might take O(k) where k is the number of elements popped, the overall number of pops across all calls is limited by n. The space complexity is O(n) because the stack can, in the worst case, store all the prices.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

For each call to `next(price)`, iterate backwards from the current day and count the number of consecutive days where the price was less than or equal to the current price.

Time: O(n^2), where n is the number of calls to next(). Each call to next() would take O(n) time.Space: O(n), to store the prices seen so far.

Trade-offs: The brute force approach is simple to understand but inefficient. It should be avoided due to its high time complexity. It might be considered if memory constraints are extremely tight and n is very small.

✨

Key Insights

1Insight 1: The key insight is that we need to efficiently find the number of consecutive days before the current day where the price was less than or equal to the current day's price.
2Insight 2: A stack is the appropriate data structure to maintain a decreasing sequence of prices and their spans encountered so far. This allows us to quickly determine the span for the current day.
3Insight 3: The stack stores pairs of (price, span) for previous days. When a new price comes in, we pop elements from the stack whose price is less than or equal to the current price. The span of the current price is then the sum of the spans of the popped elements plus 1 (for the current day).

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Increasing prices (e.g., 10, 20, 30, 40, 50). In this case, the stack will always contain all the previous prices, and each call to `next` will have a span of 1 until the stack is cleared or a smaller price is seen.
Edge case 2: Decreasing prices (e.g., 50, 40, 30, 20, 10). In this case, each call to `next` will pop all previous prices from the stack, leading to large spans.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using a stack or using an incorrect data structure. A stack is crucial for efficiently keeping track of the potential span.

✗Common mistake 2: Not correctly calculating the span. Remember to add the spans of all popped elements and add 1 for the current day.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing stock market trends. The span can indicate the strength of a price trend. A large span suggests a strong upward trend (if we are looking at prices exceeding a certain threshold), while a small span suggests a weaker trend.

🏦Real-world scenario 2: Monitoring website traffic. The 'span' could represent the duration of a period where website traffic remained above a certain threshold. This can help identify periods of high engagement and potential server load issues.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Stacks are perfect for problems involving matching (parentheses) or "next greater element" patterns. If you need to look back at recent elements, think stack.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Popping from an empty stack. Always check if the stack is non-empty before popping.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 2, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

What is a monotonic stack and when should I use it?

A monotonic stack maintains elements in sorted order (increasing or decreasing). Use it for "next greater element," "largest rectangle," or "stock span" problems. It achieves O(n) time by avoiding redundant comparisons through maintaining order invariants.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Online Stock Span"?

For this medium-level Stack problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether design techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?