🚀 Solving the Stock Span Problem - My Thought Process & Approach

GFG QUESTION LINK

LEETCODE

📌 Problem Statement

Given a series of daily stock prices, we need to find the span of stock price for each day. The span for a day i is defined as the maximum number of consecutive days before (and including) day i for which the stock price is less than or equal to its price on day i.

Example:

Input: [100, 80, 60, 70, 60, 75, 85] Output: [1, 1, 1, 2, 1, 4, 6] 

🛑 1st Attempt: Stack-Based Approach (Inefficient)

💡 Idea

I initially thought of using a stack to store previous prices, but instead of directly using it, I made a copy of the stack and iterated over it to count the span.

❌ What went wrong?

• Copying the stack every time added unnecessary complexity
• It led to O(n²) complexity and caused TLE (Time Limit Exceeded) on 6 test cases

🔻 Code

class Solution { public: vector<int> calculateSpan(vector<int>& arr) { stack<int> st; int n = arr.size(); vector<int> ans(n); for (int i = 0; i < n; i++) { int count = 1; stack<int> proxy = st; // Copying stack ❌ while (!proxy.empty() && proxy.top() < arr[i]) { proxy.pop(); count++; } ans[i] = count; st.push(arr[i]); } return ans; } }; 

🚨 Issue:

Copying the stack each time resulted in an additional O(n) operation inside a loop, making it O(n²) overall.

🔄 2nd Attempt: Two-Pointer Approach (Better, but still O(n²))

💡 Idea

I removed the stack and instead used a backward pointer (j) to find the span for each element.

❌ What went wrong?

• Still O(n²) in the worst case (when elements are in increasing order).
• Failed 1 test case due to TLE (1115/1116 passed).

🔻 Code

class Solution { public: vector<int> calculateSpan(vector<int>& arr) { int n = arr.size(); vector<int> ans; for (int i = 0; i < n; i++) { int count = 1; int j = i; while (j > 0 && arr[j - 1] <= arr[i]) { // Checking all previous elements ❌ j--; count++; } ans.push_back(count); } return ans; } }; 

🚨 Issue:

Although better than the first approach, the worst-case scenario (increasing order of prices) still made it O(n²).

✅ Final Attempt: Optimized Stack-Based Approach (O(n) Time Complexity)

💡 Key Insight

Instead of storing only prices, I stored both the price and the count as {price, count} pairs in the stack.

✨ Why This Works?

• Instead of iterating over previous elements, we store their spans directly in the stack.
• When popping elements, we directly add their span count to the current span instead of rechecking them.
• This ensures O(n) complexity as each element is processed only once.

🔥 Final Optimized Code

class Solution { public: vector<int> calculateSpan(vector<int>& arr) { stack<pair<int, int>> st; int n = arr.size(); vector<int> ans(n); for (int i = 0; i < n; i++) { int count = 1; while (!st.empty() && st.top().first <= arr[i]) { count += st.top().second; // Directly add stored counts ✅ st.pop(); } st.push({arr[i], count}); ans[i] = count; } return ans; } }; 

🚀 Time Complexity: O(n)

Each element is processed only once, making this approach highly efficient.

🔥 Key Learnings & Takeaways

1️⃣ Avoid redundant operations – Copying the stack (or unnecessary iterations) adds overhead.

2️⃣ Store useful data smartly – Instead of recalculating spans, storing counts in the stack saved time.

3️⃣ Use data structures efficiently – Leveraging a monotonic stack made the solution significantly faster.

✨ Conclusion

The journey from O(n²) to O(n) was all about optimizing how we track previous values. Using a stack efficiently made all the difference!

💡 What do you think about this approach? Have you solved this problem differently? Let’s discuss in the comments! 🚀