🚀 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! 🚀