Stock Span

1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing the prices of a share on n days. 3. You are required to find the stock span for n days. 4. Stock span is defined as the number of days passed between the current day and the first day before today when price was higher than today

I/P: { 2, 5, 9, 3, 1, 12, 6, 8, 7}

O/P: 1 2 3 1 1 6 1 2 1

import java.util.Stack;

public class Stock_Span {
    public static void main(String[] args) {
        int[] arr = {2, 5, 9, 3, 1, 12, 6, 8, 7};

        for (int x : calculate(arr)) {
            System.out.print(x + "\t");
        }
    }

    private static int[] calculate(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            // we will pop the index from stack, jab tak humein largest element nhi milta
            // or stack empty nhi ho jaata
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i])
                stack.pop();
            int largestIndex = stack.isEmpty() ? -1 : stack.peek();
            // span = current_index - largest_index
            int span = i - (largestIndex);
            ans[i] = span;
            // we will push the highest value, index
            stack.push(i);
        }
        return ans;
    }
}

 

Time Complexity:

You'll have to figure out why it's O(n). Let's take a look at one element's life cycle. Every element in the stack will be pushed into it once. In addition, the element will only be popped one time. Because it is lost from the stack once it is popped. As a result, each element is linked to two events. There was only one push and one pop. Both are operations that take place in the same amount of time. When we do the same thing with n elements, we get n*O(1), or O(n) operations. As a result, the time complexity is O(n).

Space Complexity:

We're using an auxiliary stack, which will be completely filled with n numbers in the worst-case scenario. Could you please explain what that is? If the numbers are in ascending order, yes. There will be nothing to pop then, only elements to push. There's also a span array where we had to store the span results. As a result, the overall space complexity is O(n).