Stock Span Problem
The Stock Span Problem is a financial problem where we are given an array of daily stock prices for a stock, and we need to calculate the span of stock's price for each day. The span of the stock's price for a particular day is defined as the maximum number of consecutive days (including the current day) for which the price of the stock on those days is less than or equal to the price on the current day.
Problem Statement
Given an array rates representing the stock prices for each day, the task is to calculate the stock
span for each day and store it in an array stockspan, where stockspan[i] represents
the stock span of the stock price on the i-th day.
Example
Consider the following array representing the stock prices for six consecutive days:
rates = [7, 13, 25, 12, 41, 9]
The stock span for each day will be:
stockspan = [1, 2, 3, 1, 5, 1]Idea to Solve the Problem
To calculate the stock span for each day, we can use a stack data structure. The stack will be used to keep track
of the indices of the stock prices in the rates array. We will iterate through the
rates array and for each element, we will compare it with the elements at the indices stored in the
stack. If the current element is greater than the element at the top of the stack, we will pop elements from the
stack until the current element is less than or equal to the element at the top of the stack. The span of the
current element will be the difference between its index and the index of the element remaining at the top of
the stack. Then, we push the current element's index into the stack. By doing this, we ensure that the stack
always contains indices of elements in decreasing order.
Pseudocode
Function findSpan(rates, stockspan, days):
Create a stack stack
Set stockspan[0] = 1
Push 0 into stack
Iterate i from 1 to days-1:
While stack is not empty and rates[stack.top] <= rates[i]:
Pop element from stack
If stack is empty:
Set stockspan[i] = i + 1
Else:
Set stockspan[i] = i - stack.top
Push i into stack
Algorithm
- Create an empty stack
stackto hold the indices of the elements. - Set
stockspan[0] = 1since the span of the first day is always 1. - Push the index
0into the stack. - Iterate from
i = 1toi = days - 1(wheredaysis the number of days). a. While the stack is not empty andrates[stack.top] <= rates[i], pop elements from the stack. b. If the stack is empty, setstockspan[i] = i + 1, as there are no elements on the left side that are greater thanrates[i]. c. Otherwise, setstockspan[i] = i - stack.top, which represents the span ofrates[i]with respect to the element at indexstack.top. d. Push the indexiinto the stack. - The array
stockspanwill contain the stock span for each day.
Code Solution
// C program
// The Stock Span Problem
#include <stdio.h>
#include <stdlib.h>
// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = next;
}
return node;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
// Add stack element
stack->top = newNode(element, stack->top);
stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Calculating the stock span
void findSpan(int rates[], int stockspan[], int days)
{
// Create an stack
struct MyStack *stack = newStack();
// Set initial value
stockspan[0] = 1;
push(stack, 0);
// iterating through the days
for (int i = 1; i < days; ++i)
{
while (isEmpty(stack) == 0 && rates[peek(stack)] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
pop(stack);
}
if (isEmpty(stack) == 1)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - peek(stack);
}
// Add element into stack
push(stack, i);
}
}
// Display calculate elements
void display(int stockspan[], int days)
{
for (int i = 0; i < days; ++i)
{
// Print elements
printf(" %d", stockspan[i]);
}
printf("\n");
}
int main()
{
int rates[] = {
7 , 13 , 25 , 12 , 41 , 9
};
// Get the number of elements
int days = sizeof(rates) / sizeof(rates[0]);
int stockspan[days];
findSpan(rates, stockspan, days);
display(stockspan, days);
return 0;
}Output
1 2 3 1 5 1/*
Java Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class StockSpanProblem
{
// Calculating the stock span
public void findSpan(int[] rates, int[] stockspan, int days)
{
// Create an stack
MyStack stack = new MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
// iterating through the days
for (int i = 1; i < days; ++i)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
}
}
// Display calculate elements
public void display(int[] stockspan, int days)
{
for (int i = 0; i < days; ++i)
{
// Print elements
System.out.print(" " + stockspan[i]);
}
System.out.print("\n");
}
public static void main(String[] args)
{
StockSpanProblem task = new StockSpanProblem();
int[] rates = {
7 , 13 , 25 , 12 , 41 , 9
};
// Get the number of elements
int days = rates.length;
int[] stockspan = new int[days];
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
}
}Output
1 2 3 1 5 1// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
public:
int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public:
StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
delete temp;
temp = NULL;
this->size--;
}
}
// return top element of stack
int peek()
{
return this->top->element;
}
};
class StockSpanProblem
{
public:
// Calculating the stock span
void findSpan(int rates[], int stockspan[], int days)
{
// Create an stack
MyStack stack = MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
// iterating through the days
for (int i = 1; i < days; ++i)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
}
}
// Display calculate elements
void display(int stockspan[], int days)
{
for (int i = 0; i < days; ++i)
{
// Print elements
cout << " " << stockspan[i];
}
cout << "\n";
}
};
int main()
{
StockSpanProblem task = StockSpanProblem();
int rates[] = {
7 , 13 , 25 , 12 , 41 , 9
};
// Get the number of elements
int days = sizeof(rates) / sizeof(rates[0]);
int stockspan[days];
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
return 0;
}Output
1 2 3 1 5 1// Include namespace system
using System;
/*
C# Program
The Stock Span Problem
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
return this.top.element;
}
}
public class StockSpanProblem
{
// Calculating the stock span
public void findSpan(int[] rates, int[] stockspan, int days)
{
// Create an stack
MyStack stack = new MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
// iterating through the days
for (int i = 1; i < days; ++i)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
}
}
// Display calculate elements
public void display(int[] stockspan, int days)
{
for (int i = 0; i < days; ++i)
{
// Print elements
Console.Write(" " + stockspan[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
StockSpanProblem task = new StockSpanProblem();
int[] rates = {
7 , 13 , 25 , 12 , 41 , 9
};
// Get the number of elements
int days = rates.Length;
int[] stockspan = new int[days];
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
}
}Output
1 2 3 1 5 1<?php
/*
Php Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
public $element;
public $next;
function __construct($element, $next)
{
$this->element = $element;
$this->next = $next;
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
//Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($element)
{
$this->top = new StackNode($element, $this->top);
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
return $this->top->element;
}
}
class StockSpanProblem
{
// Calculating the stock span
public function findSpan( & $rates, & $stockspan, $days)
{
// Create an stack
$stack = new MyStack();
// Set initial value
$stockspan[0] = 1;
$stack->push(0);
// iterating through the days
for ($i = 1; $i < $days; ++$i)
{
while ($stack->isEmpty() == false && $rates[$stack->peek()] <= $rates[$i])
{
// When the top of stack element is less than equal to rates of i location
$stack->pop();
}
if ($stack->isEmpty() == true)
{
//When stack is empty
$stockspan[$i] = $i + 1;
}
else
{
$stockspan[$i] = $i - $stack->peek();
}
// Add element into stack
$stack->push($i);
}
}
// Display calculate elements
public function display( & $stockspan, $days)
{
for ($i = 0; $i < $days; ++$i)
{
// Print elements
echo " ". $stockspan[$i];
}
echo "\n";
}
}
function main()
{
$task = new StockSpanProblem();
$rates = array(7, 13, 25, 12, 41, 9);
// Get the number of elements
$days = count($rates);
$stockspan = array_fill(0, $days, 0);
$task->findSpan($rates, $stockspan, $days);
$task->display($stockspan, $days);
}
main();Output
1 2 3 1 5 1/*
Node Js Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
return this.top.element;
}
}
class StockSpanProblem
{
// Calculating the stock span
findSpan(rates, stockspan, days)
{
// Create an stack
var stack = new MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
// iterating through the days
for (var i = 1; i < days; ++i)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
}
}
// Display calculate elements
display(stockspan, days)
{
for (var i = 0; i < days; ++i)
{
// Print elements
process.stdout.write(" " + stockspan[i]);
}
process.stdout.write("\n");
}
}
function main()
{
var task = new StockSpanProblem();
var rates = [7, 13, 25, 12, 41, 9];
// Get the number of elements
var days = rates.length;
var stockspan = Array(days).fill(0);
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
}
main();Output
1 2 3 1 5 1# Python 3 Program
# The Stock Span Problem
# Define stack node
class StackNode :
def __init__(self, element, next) :
self.element = element
self.next = next
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
return self.top.element
class StockSpanProblem :
# Calculating the stock span
def findSpan(self, rates, stockspan, days) :
# Create an stack
stack = MyStack()
# Set initial value
stockspan[0] = 1
stack.push(0)
i = 1
# iterating through the days
while (i < days) :
while (stack.isEmpty() == False and rates[stack.peek()] <= rates[i]) :
# When the top of stack element is less than equal to rates of i location
stack.pop()
if (stack.isEmpty() == True) :
# When stack is empty
stockspan[i] = i + 1
else :
stockspan[i] = i - stack.peek()
# Add element into stack
stack.push(i)
i += 1
# Display calculate elements
def display(self, stockspan, days) :
i = 0
while (i < days) :
# Print elements
print(" ", stockspan[i], end = "")
i += 1
print(end = "\n")
def main() :
task = StockSpanProblem()
rates = [7, 13, 25, 12, 41, 9]
# Get the number of elements
days = len(rates)
stockspan = [0] * (days)
task.findSpan(rates, stockspan, days)
task.display(stockspan, days)
if __name__ == "__main__": main()Output
1 2 3 1 5 1# Ruby Program
# The Stock Span Problem
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, top)
self.element = element
self.next = top
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
return self.top.element
end
end
class StockSpanProblem
# Calculating the stock span
def findSpan(rates, stockspan, days)
# Create an stack
stack = MyStack.new()
# Set initial value
stockspan[0] = 1
stack.push(0)
i = 1
# iterating through the days
while (i < days)
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
# When the top of stack element is less than equal to rates of i location
stack.pop()
end
if (stack.isEmpty() == true)
# When stack is empty
stockspan[i] = i + 1
else
stockspan[i] = i - stack.peek()
end
# Add element into stack
stack.push(i)
i += 1
end
end
# Display calculate elements
def display(stockspan, days)
i = 0
while (i < days)
# Print elements
print(" ", stockspan[i])
i += 1
end
print("\n")
end
end
def main()
task = StockSpanProblem.new()
rates = [7, 13, 25, 12, 41, 9]
# Get the number of elements
days = rates.length
stockspan = Array.new(days) {0}
task.findSpan(rates, stockspan, days)
task.display(stockspan, days)
end
main()Output
1 2 3 1 5 1
/*
Scala Program
The Stock Span Problem
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): Int = {
return this.top.element;
}
}
class StockSpanProblem
{
// Calculating the stock span
def findSpan(rates: Array[Int], stockspan: Array[Int], days: Int): Unit = {
// Create an stack
var stack: MyStack = new MyStack();
// Set initial value
stockspan(0) = 1;
stack.push(0);
var i: Int = 1;
// iterating through the days
while (i < days)
{
while (stack.isEmpty() == false && rates(stack.peek()) <= rates(i))
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan(i) = i + 1;
}
else
{
stockspan(i) = i - stack.peek();
}
// Add element into stack
stack.push(i);
i += 1;
}
}
// Display calculate elements
def display(stockspan: Array[Int], days: Int): Unit = {
var i: Int = 0;
while (i < days)
{
// Print elements
print(" " + stockspan(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: StockSpanProblem = new StockSpanProblem();
var rates: Array[Int] = Array(7, 13, 25, 12, 41, 9);
// Get the number of elements
var days: Int = rates.length;
var stockspan: Array[Int] = Array.fill[Int](days)(0);
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
}
}Output
1 2 3 1 5 1/*
Swift 4 Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ next: StackNode? )
{
self.element = element;
self.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->Int
{
return self.top!.element;
}
}
class StockSpanProblem
{
// Calculating the stock span
func findSpan(_ rates: [Int], _ stockspan: inout[Int], _ days: Int)
{
// Create an stack
let stack: MyStack = MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
var i: Int = 1;
// iterating through the days
while (i < days)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
i += 1;
}
}
// Display calculate elements
func display(_ stockspan: [Int], _ days: Int)
{
var i: Int = 0;
while (i < days)
{
// Print elements
print(" ", stockspan[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
let task: StockSpanProblem = StockSpanProblem();
let rates: [Int] = [7, 13, 25, 12, 41, 9];
// Get the number of elements
let days: Int = rates.count;
var stockspan: [Int] = Array(repeating: 0, count: days);
task.findSpan(rates, &stockspan, days);
task.display(stockspan, days);
}
main();Output
1 2 3 1 5 1/*
Kotlin Program
The Stock Span Problem
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, next: StackNode ? )
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): Int
{
return this.top!!.element;
}
}
class StockSpanProblem
{
// Calculating the stock span
fun findSpan(rates: Array<Int>, stockspan: Array<Int>, days: Int): Unit
{
// Create an stack
var stack: MyStack = MyStack();
// Set initial value
stockspan[0] = 1;
stack.push(0);
var i: Int = 1;
// iterating through the days
while (i<days)
{
while (stack.isEmpty() == false && rates[stack.peek()] <= rates[i])
{
// When the top of stack element is less than equal to rates of i location
stack.pop();
}
if (stack.isEmpty() == true)
{
//When stack is empty
stockspan[i] = i + 1;
}
else
{
stockspan[i] = i - stack.peek();
}
// Add element into stack
stack.push(i);
i += 1;
}
}
// Display calculate elements
fun display(stockspan: Array<Int>, days: Int): Unit
{
var i: Int = 0;
while (i<days)
{
// Print elements
print(" " + stockspan[i]);
i += 1;
}
print("\n");
}
}
fun main(args: Array<String>): Unit
{
var task: StockSpanProblem = StockSpanProblem();
var rates: Array<Int> = arrayOf(7, 13, 25, 12, 41, 9);
// Get the number of elements
var days: Int = rates.count();
var stockspan: Array<Int> = Array(days)
{
0
};
task.findSpan(rates, stockspan, days);
task.display(stockspan, days);
}Output
1 2 3 1 5 1Time Complexity
The time complexity of the algorithm is O(N), where N is the number of days. This is because each element is processed once and pushed/popped from the stack at most once. Therefore, the time complexity is linear with respect to the number of days.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment