Stack

Stock Span Problem

Rajeev SinghAlgorithms1 mins read

Stock Span Problem

Problem Statement

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.

The span S[i] of the stock’s price on a given day i is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to its price on day i.

For example, if the price of a stock over a period of 7 days are [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Explanation

Stock price    Max Consecutive days (starting from today) for which the stock price was 
               less than or equal to the current price

100            1
80             1
60             1
70             2
60             1
75             4
85             6

Solution

Brute Force

import java.util.Scanner;
import java.util.Stack;

class StockSpanProblem {
    private static int[] stockSpan(int[] stockPrices) {
        int n = stockPrices.length;
        int[] span = new int[n];

        for(int i = 0; i < n; i++) {
            span[i] = 1;
            for(int j = i-1; j >= 0; j--) {
                if(stockPrices[j] <= stockPrices[i]) {
                    span[i]++;
                } else {
                    break;
                }
            }
        }

        return span;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] stockPrices = new int[n];
        for (int i = 0; i < n; i ++) {
            stockPrices[i] = keyboard.nextInt();
        }
        keyboard.close();

        int[] span = stockSpan(stockPrices);
        for(int i = 0; i < n; i++) {
            System.out.print(span[i] + " ");
        }
        System.out.println();
    }
}

Time Complexity: O(n^2) Space Complexity: O(1)

Using Stack

import java.util.Scanner;
import java.util.Stack;

class StockSpanProblem {
    private static int[] findNearestGreaterToLeftUsingStack(int[] stockPrices) {
        int n = stockPrices.length;
        int[] NGL = new int[n];
        Stack<Integer> s = new Stack<>();

        for(int i = 0; i < n; i++) {
            NGL[i] = -1;
            while(!s.empty()) {
                int top = s.peek();
                if(stockPrices[top] > stockPrices[i]) {
                    NGL[i] = top;
                }
            }
            s.push(i);
        }

        return NGL;
    }

    private static int[] stockSpanUsingStack(int[] stockPrices) {
        int[] NGL = findNearestGreaterToLeftUsingStack(stockPrices);
        int[] span = new int[NGL.length];
        for(int i = 0; i < NGL.length; i++) {
            span[i] = i - NGL[i];
        }
        return span;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] stockPrices = new int[n];
        for (int i = 0; i < n; i ++) {
            stockPrices[i] = keyboard.nextInt();
        }
        keyboard.close();

        int[] span = stockSpan(stockPrices);
        for(int i = 0; i < n; i++) {
            System.out.print(span[i] + " ");
        }
        System.out.println();
    }
}

Time Complexity: O(n), The entire array (of size n) is scanned only once. Each of the stack’s n elements are pushed and popped exactly once.

Space Complexity: O(n)