Stock Span Problem Using Stack in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Stock Span Problem?

It is a problem where for each day, we find how many consecutive previous days had stock prices less than or equal to the current day's price.

intermediate

Why do we use a stack to solve the Stock Span Problem?

A stack helps keep track of previous days with higher stock prices efficiently, allowing us to find spans in O(n) time instead of O(n²).

intermediate

What does each element in the stack represent in the Stock Span Problem?

Each element in the stack stores the index of a day with a stock price greater than the current day's price.

intermediate

How is the span for a day calculated using the stack?

Span = current day index - index of last higher price day (top of stack) or current day index + 1 if stack is empty.

intermediate

What is the time complexity of the Stock Span Problem solution using a stack?

The time complexity is O(n) because each element is pushed and popped at most once.

What does the stack store in the Stock Span Problem?

A Stock prices themselves

B Indices of days with higher stock prices

C Span values

D Sum of stock prices

The stack stores indices of days with higher stock prices to help calculate spans efficiently.

If the stack is empty when calculating span for day i, what is the span?

A i + 1

B 0

C 1

D i

If no previous higher price day exists, span is all days up to current, i.e., i + 1.

What is the worst-case time complexity of the naive Stock Span solution without stack?

A O(n²)

B O(n log n)

C O(n)

D O(log n)

Naive approach checks all previous days for each day, leading to O(n²) time.

What operation is performed on the stack when current day's price is higher than top of stack's day price?

A Do nothing

B Push current day index

C Pop from stack

D Clear stack

We pop days with lower or equal prices to find the last higher price day.

What data structure is best suited for solving the Stock Span Problem efficiently?

A Array only

B Queue

C Linked List

D Stack

Stack allows efficient tracking of previous higher prices for O(n) solution.

Explain how the stack helps in calculating the stock span for each day.

Think about how to find the last day with a higher price before the current day.

Describe the step-by-step process to solve the Stock Span Problem using a stack.

Focus on how the stack changes as you move through days.