# The Market Streak

> Some stocks run longer than you think.

Canonical URL: <https://datadriven.io/problems/the_market_streak>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of daily prices, return a list of the same length. Position i holds the count of consecutive days ending at day i where the price was <= prices[i] (including day i itself).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **monotonic stack pattern**, which is the optimal approach for span/next-greater-element problems. Interviewers use it to check whether candidates recognize the pattern and can implement it efficiently instead of brute-forcing with nested loops.

> **Trick to Solving**
>
> When you see 'consecutive days where price was lower or equal', think monotonic stack. The stack stores indices of unresolved previous days. When today's price exceeds a stacked day, that day's span is resolved. This avoids re-scanning past prices.

---

### Break down the requirements

#### Step 1: Initialize a stack and result array

The stack holds indices of days whose spans are not yet determined. The result array starts with span 1 for each day (every day counts itself).

#### Step 2: For each day, pop smaller-or-equal prices

While the stack is non-empty and the price at the top index is less than or equal to today's price, pop it. Each pop means that day's span extends to today.

#### Step 3: Compute the span from the stack top

If the stack is empty, the span is `i + 1` (all previous days had lower or equal prices). Otherwise, the span is `i - stack[-1]`.

#### Step 4: Push the current index

Today becomes a candidate for future span calculations.

---

### The solution

**Monotonic stack for span calculation**

```python
def stock_span(prices):
    spans = [0] * len(prices)
    stack = []
    for i in range(len(prices)):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        if not stack:
            spans[i] = i + 1
        else:
            spans[i] = i - stack[-1]
        stack.append(i)
    return spans
```

> **Time and Space Complexity**
>
> **Time:** O(n). Each index is pushed and popped at most once, so the total work across all iterations is linear.
> 
> **Space:** O(n) for the stack in the worst case (strictly decreasing prices).

> **Interviewers Watch For**
>
> Can you explain why the amortized time is O(n) despite the inner while loop? The key insight is that each element enters and leaves the stack at most once across the entire execution.

> **Common Pitfall**
>
> Using `<` instead of `<=` in the comparison. The problem says 'less than or equal to today's price', so equal prices extend the span.

---

## Common follow-up questions

- How would you handle this as a streaming problem where prices arrive one at a time? _(Tests maintaining the stack as persistent state across calls.)_
- What if you also needed the maximum span across all days? _(Tests adding a running max tracker alongside the stack.)_
- How does this relate to the 'next greater element' problem? _(Tests recognizing monotonic stack as a general pattern family.)_
- What if prices could be floating-point with precision issues? _(Tests awareness of float comparison pitfalls.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_market_streak)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.