Stock Span problem using JavaScript
The stock span problem involves determining the consecutive days before each day where the stock price was less than or equal to the current day’s price. This algorithm efficiently calculates the stock spans using a stack-based approach, iterating through the prices array and maintaining a stack of indices representing previous days. The resulting span array indicates the span of each day’s stock price relative to previous days.
Below are the approaches to solve the Stock Span problem using JavaScript
Table of Content
- Using stack
- Using Array
- Using dynamic programming
Using stack
This JavaScript function efficiently calculates the stock span for each day in an array of stock prices using a stack-based approach. It iterates through the prices array, maintaining a stack of indices representing previous days. For each day, it compares the current price with the previous ones stored in the stack, popping elements until finding a price less than the current day. The resulting span array represents the number of consecutive days before the current day with prices less than or equal to the current day’s price.
Example: The code below shows the Stock Span problem using JavaScript using stack.
function calculateSpan(prices) {
const n = prices.length;
const stack = [];
const span = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
while (stack.length > 0 &&
prices[stack[stack.length - 1]]
<= prices[i]) {
stack.pop();
}
span[i] = stack.length === 0 ? i + 1 : i -
stack[stack.length - 1];
stack.push(i);
}
return span;
}
const prices = [100, 80, 60, 70, 60, 75, 85];
console.log(calculateSpan(prices));
Output
[ 1, 1, 1, 2, 1, 4, 6 ]
Time Complexity: O(n), where n is the number of elements in the prices array.
Space Complexity: O(n) since we use an additional stack to store indices.
Using Array
This JavaScript function calculates the stock span for each day in an array of stock prices. It iterates through the prices array, comparing each price with the previous ones to determine the span. The resulting spans array represents the number of consecutive days before the current day with prices less than or equal to the current day’s price.
Example: The code below shows Stock Span problem using JavaScript Using Array.
function stockSpan(prices) {
const spans = new Array(prices.length).fill(1);
for (let i = 1; i < prices.length; i++) {
let span = 1;
// Compare the current price with previous prices
for (let j = i - 1; j >= 0 &&
prices[i] >= prices[j]; j--) {
span++;
}
spans[i] = span;
}
return spans;
}
const prices = [100, 80, 60, 70, 60, 75, 85];
console.log(stockSpan(prices));
Output
[ 1, 1, 1, 2, 1, 4, 6 ]
Time complexity: O(n^2)
Space complexity: O(n)
Using dynamic programming
Since the same subproblems are called again, this problem has the Overlapping Subproblems property. S0, the recomputations of the same subproblems can be avoided by constructing a temporary array to store already calculated answers
- Store the answer for every index in an array and calculate the value of the next index using previous values
- i.e check the answer for previous element and if the value of the current element is greater than the previous element
- Add the answer to the previous index into current answer and then check the value of (previous index – answer of previous index)
- Check this condition repeatedly
Below is the implementation of the above approach:
// JavaScript program for the above approach
// An efficient method to calculate stock span values
// implementing the same idea without using stack
function calculateSpan(A, n, ans) {
// Span value of first element is always 1
ans[0] = 1;
// Calculate span values for rest of the elements
for (let i = 1; i < n; i++) {
let counter = 1;
while ((i - counter) >= 0 && A[i] >= A[i - counter]) {
counter += ans[i - counter];
}
ans[i] = counter;
}
}
// A utility function to print elements of array
function printArray(arr, n) {
let result = "";
for (let i = 0; i < n; i++) {
result += arr[i] + " ";
}
return result;
}
// Driver program to test above function
let price = [10, 4, 5, 90, 120, 80];
let n = price.length;
let S = new Array(n);
// Fill the span values in array S[]
calculateSpan(price, n, S);
// Print the calculated span values
console.log(printArray(S, n));
Output
1 1 2 4 5 1
Time Complexity: O(N)
Auxiliary Space: O(N)