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

Recall & Review

beginner

What is the Stock Span Problem?

The Stock Span Problem finds, for each day, 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 by popping smaller prices until a higher price is found.

intermediate

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

Each element in the stack stores a pair: (index of the day, stock price on that day). This helps calculate the span by comparing prices and indices.

intermediate

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

Span = current day index - index of the last higher price day found on the stack. If no higher price day exists, span = current day index + 1.

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 from the stack.

What does the stack store in the Stock Span Problem?

A Pairs of (day index, stock price)

B Only stock prices

C Only day indices

D Pairs of (stock price, span)

The stack stores pairs of (day index, stock price) to help calculate spans efficiently.

What is the span for the first day in the stock span problem?

A Depends on price

B 0

C 1

D Same as second day

The first day always has a span of 1 because there are no previous days.

If the current day's price is less than the price at the top of the stack, what do we do?

A Pop from stack

B Push current day onto stack

C Ignore current day

D Clear the stack

We push the current day onto the stack because it is a new higher price boundary.

What is the time complexity of the stack-based solution for the Stock Span Problem?

A O(n)

B O(n log n)

C O(log n)

D O(n^2)

Each element is pushed and popped at most once, so the solution runs in O(n) time.

What happens when the stack is empty while calculating the span for a day?

A Span is zero

B Span is previous day's span

C Span is 1

D Span is current day index + 1

If the stack is empty, it means no previous higher price exists, so span = current day index + 1.

Explain how a stack helps solve the Stock Span Problem efficiently.

Think about how you find the last day with a higher price.

Describe the step-by-step process to calculate the span for each day using a stack.

Imagine you are checking previous days one by one but faster.