Why Stock Span Problem Using Stack in DSA C?

The Big Idea

Discover how a simple stack can save you hours of tedious price comparisons!

The Scenario

Imagine you are tracking daily stock prices on paper. For each day, you want to know how many consecutive previous days had prices less than or equal to today's price.

Doing this by checking every previous day manually for each new price is tiring and slow.

The Problem

Manually comparing today's price with all previous days for every new price means repeating many checks again and again.

This takes a lot of time and can easily cause mistakes, especially with many days of data.

The Solution

Using a stack helps keep track of previous days with higher prices efficiently.

This way, you only compare with relevant days, skipping unnecessary checks and speeding up the process.

Before vs After

✗ Before

for (int i = 0; i < n; i++) {
  span[i] = 1;
  for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; j--) {
    span[i]++;
  }
}

✓ After

stack<int> s;
for (int i = 0; i < n; i++) {
  while (!s.empty() && prices[s.top()] <= prices[i]) {
    s.pop();
  }
  span[i] = s.empty() ? (i + 1) : (i - s.top());
  s.push(i);
}

What It Enables

This method allows quick calculation of stock spans for large data sets, enabling fast financial analysis.

Real Life Example

Traders use this to quickly understand how many days in a row a stock price has been rising or stable, helping them decide when to buy or sell.

Key Takeaways

Manual checking repeats many comparisons and is slow.

Stack stores indices of days with higher prices to skip unnecessary checks.

Efficiently calculates spans in one pass through the data.