Stock Span Problem Using Stack in Java

The stock span problem is an issue in finance where we must determine a stock’s price span over all N days given a set of N daily price quotes. The maximum number of days before a particular day for which the stock price on the current day is less than the given day is known as the span Si of the stock's price on that day.

The financial element includes "The Stock Span Problem." This task determines the stock span for each day's stock price. The longest stretch of days preceding a specific day when the stock price is lower than or the same as the stock price on those days is known as the gap. The span Si of the stock's price on that day is defined as the maximum number of days just before the given day for which the stock's price today is less than or equal to its price on the given day.

Problem Statement

A list of a stock's prices for N days is provided. Find the stack span for each day is the problem at hand.

The stock gap is K before the number of days before the current day that the stock price was either equal to or lower than the present price.

Example 1

N = 7, and the stock_price[] = [101 85 61 73 66 77 110]

Output:

 [1 1 1 2 1 4 7 ]

Explanation: When traversing the input given, the span for 101 will be 1, 85 will be less than 101, 61 will be less than 80, 73 will be higher than 61, and 66 will be smaller than 73. Finally, since the span is and 110 is more than all of the elements, the result will be 1 1 1 2 1 4 6.

Example 2

Input: [100, 80, 60, 70, 60, 75, 85]

Output : [1, 1, 1, 2, 1, 4, 6] 

Explanation:

There is no prior day for which the stock price was less than or equal to day 1's price of 100. The span is, therefore, 1.

There is no prior day where the price was less than or equal to day 2's price of 80 for the stock. The span is, therefore, 1.

There is no prior day where the price was less than or equal to day 3's price of 60 for the stock. The span is, therefore, 1.

The stock's price on day 4 is 70, and day 3's stock price of 60 is less than or equal to day 4's stock price (70). hence, the spread is two (as there are two consecutive days, day 3 and day 4, for which the stock price is less than or equal to 70).

The stock is priced at 60 for day 5, while day 4's stock price (70) was higher than day 5's price (60). The span is, therefore, 1.

For day 6, the stock price is 75, and the stock on day 5 (60) is less than or equal to day 6 (75). Hence, the span is 4 (as there are four consecutive days, day 3, day 4, day 5, and day 6, for which the stock price is less than or equal to 75).

For day 7, the stock price is 85, and the stock on day 6 (75) is less than or equal to the price on day 7 (85). Hence, the span is 6 (as there are six consecutive days, day 2, day 3, day 4, day 5, day 6, and day 7, for which the stock price is less than or equal to 85).

Naïve Approach

The stock span problem seeks to identify the number of days a stock has been able to remain at or above a certain price. This problem can be solved using a brute force approach, which involves looping through each day in the stock data and counting the days that the price remains at or above the given price. The brute force approach would require looping through the stock data multiple times and could become computationally expensive if the data set is large.

Main.java

import java.util.Arrays;
class Main
{
	static void spanCaluclate(int price[], int n, int S[])
	{
		S[0] = 1;
		for (int i = 1; i < n; i++) {
			S[i] = 1; 
			for (int j = i - 1;
				(j >= 0) && (price[i] >= price[j]); j--)
				S[i]++;
		}
	}
	static void printArray(int arr[])
	{
		System.out.print(Arrays.toString(arr));
	}
// Main section of the program where execution begins
	public static void main(String[] s)
	{
		// stock array declaration
		int stock[] = { 10, 5, 4, 91, 89, 99 };
		// finding the length of the stock array 
		int l = stock.length;
		// creating an array to store the span values
		int arr[] = new int[l];
		// Fill the span values in array arr[]
		spanCaluclate(stock, l, arr);
		// printing the array
		System. out.println("The stock span array is ");
		printArray(arr);
	}
}

Output

The stock span array is 
[1, 1, 1, 4, 1, 6]

Approach Using Stacks

We can see that S[i] on the day i can be calculated easily if we know the day that is immediately prior beforehand. The price is higher on that day than on the day i. Let's call such a day h(i) if it exists; else, we define h(i) = -1.

S[i] = i - h is now used to calculate the span (i).

We utilize a stack as an abstract data type to store the days I h(i), h(h(i)), and so on to put this logic into practice. When moving from day i-1 today i, we push the value of day I back into the stack after popping the days when the stock price was less than or equal to price[i].

Pseudo Code

• Make an int stack and place 0 in it.
• Set the response on day 1 as 1, then iterate through the days using a loop.
• Pop out the top value as long as the stack is not empty and the price of st. to p is lower than or equal to the price of the current day.
• Set the current day's response to i+1. If the stack is full; otherwise, i - st. top
• Place today on top of the stack.
• Print the solution utilizing the solution array.

Note: We must also consider the possibility that all stock prices should be equal, in which case we must only determine whether the current stock price is higher than the prior one. We won't pop from the stack when the stock price is the same today as yesterday.

StockSpanProblem.java

// importing required packages
import java. util.ArrayDeque;
import java. util.Arrays;
import java. util.Deque;
// Main class declaration 
public class StockSpanProblem {
	// An effective way to calculate stock span values using stacks
	static void spanCaluclate(int price[], int n, int arr[])
	{
		// Creating  a stack and pushing the index of the array’s first element into it
		Deque<Integer> sta = new ArrayDeque<Integer>();
		sta.push(0);


		// The first element's span value is always 1.
		//Because there is no element to the right of the 1st element
		arr[0] = 1;
		// calculating the span values for the remaining elements
		
		for (int j = 1; j < n; j++) {


			// When the stack is not empty, and the top is smaller than the price, remove elements[i].
			while (!sta.isEmpty() && price[sta.peek()] <= price[j])
				sta.pop();


			// Price[i] is greater than all elements to the left of it if the stack becomes empty.
		    // Otherwise, the price[i] exceeds the components below the top of the stack.
			arr[j] = (sta.isEmpty()) ? (j + 1) : (j - sta.peek());


			// Push this element to stack
			sta.push(j);
		}
	}


	// A function for printing elements of the array
	static void printArray(int arr[])
	{
		System.out.print(Arrays.toString(arr));
	}


	// Main section of the program where execution begins
	public static void main(String[] s)
	{
		// stock array declaration
		int stock[] = { 10, 5, 4, 91, 89, 99 };
		// finding the length of the stock array 
		int l = stock.length;
		// creating an array to store the span values
		int arr[] = new int[l];




		// Fill the span values in array arr[]
		spanCaluclate(stock, l, arr);
		// printing the array
		System. out.println("The stock span array is ");
		printArray(arr);
	}
}

Output

The stock span array is
[1, 1, 1, 4, 1, 6]

Complexity Analysis

The time complexity is O(N). At first glance, it seems to be more than O(N). A deeper inspection reveals that each element of the array gets added to and removed from the stack a maximum of once.

In the worst-case scenario, when all elements are arranged in decreasing order, auxiliary space is O(N).