Stock span problem

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Span = number of consecutive days <= current price ending at today. Use monotone stack of (price, span) pairs.

Algorithm

1Stack of (price, span). For each price p: span = 1. While stack not empty and stack.top.price <= p: span += stack.top.span. Pop.
2Push (p, span). Record span.

Common Pitfalls

•Store span in stack entry to avoid recomputing. Each element is processed at most twice.

Stock span problem.java

Java

// Approach: Monotonic stack storing indices. Span[i] = i - index of prev greater element (or i+1 if none).
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> calculateSpan(int[] arr) {
        ArrayList<Integer> res = new ArrayList<>();
        Stack<Integer> st = new Stack<>();

        res.add(1);
        st.push(0);
        for (int i = 1; i < arr.length; i++) {
            while (!st.isEmpty() && arr[i] >= arr[st.peek()])
                st.pop();

            if (st.isEmpty())
                res.add(i + 1);
            else
                res.add(i - st.peek());

            st.push(i);
        }

        return res;
    }
}

Was this solution helpful?