EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Stock Span Problem
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search
    • Stock Span Problem

Stock Span Problem

By Priya PedamkarPriya Pedamkar

Definition

Stock Span Problem comes under economical aspects where we have a series of the stock price quoted for a stock every day and involves calculating the span of the stock price for all number of days, the maximal number of days for which the stock price is equal to or less than the present days. In other words, it involves finding the number of days to the first day, where the stock price of the present day is higher than that of the current day. This problem is used to determine the sentiment of the market.

Stock Span Problem

Introduction to Stock Span Problem

The stock span problem is solved by using the data structures as it provides an effective and efficient way to track the maximum number of days that were successive for which the stock price was equal to or less than to given price. This is a classic problem in finance which involves determining whether the stock price is lower than the current day stock price. The goal of the stock span problem is to find the maximum no. of consecutive days, which is helpful in analyzing the trends of stock price.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

This problem is approached by using the data structures as it provides an efficient way to track the stock price. This is an essential financial concept and is widely used in the stock market for decision-making, analysis, and investment. To understand the solution and problem of the stock span, investors make the decisions to take advantage of market trends to maximize the returns of their stock.

Naive Approach – Brute Force

The naïve approach uses brute force to find the span of every stock price. This is done iteratively after counting the number of elements from the left to the right side of the current element that was equal to or greater than the current element. Below is the algorithm of naïve brute force algorithm as follows.

Algorithm:

  1. Start
  2. Traverse the price array.
  3. Run for loop for each i into the 0 to n.
    • Iterate the j elements when there is the element to the right-hand side.
    • If price j is less than the current price, then increment the count and need to decrement the j.
    • Then set the span[i] as count.
  4. Then return the array of spans.
  5. Stop

Below are the programs of the naïve approach.

C Language

Code:

#include <stdio.h>
void calspan(int pr[], int n, int S[])
{
S[0] = 1;
for (int a = 1; a < n; a++) {
S[a] = 1;
for (int b = a - 1;
(b >= 0) && (pr[a] >= pr[b]); b--)
S[a]++;
}
}
void printArray (int arr[], int n)
{
for (int a = 0; a < n; a++)
printf ("%d ", arr[a]);
}
int main()
{
int pr[] = { 13, 7, 6, 80, 150, 70 };
int n = sizeof(pr) / sizeof(pr[0]);
int S[n];
calspan(pr, n, S);
printArray(S, n);
return 0;
}

Output:

C language

Time complexity – O(N^2)

Auxiliary space – O(N)

C++ Language

Code:

#include <bits/stdc++.h>
using namespace std;
void calsp (int pr[], int n, int S[])
{
S[0] = 1;
for (int a = 1; a < n; a++) {
S[a] = 1;
for (int b = a - 1;
(b >= 0) && (pr[a] >= pr[b]); b--)
S[a]++;
}
}
void par(int arr[], int n)
{
for (int a = 0; a < n; a++)
cout << arr[a] << " ";
}
int main()
{
int pr[] = { 13, 7, 6, 80, 150, 70  };
int n = sizeof(pr) / sizeof(pr[0]);
int S[n];
calsp(pr, n, S);
par(S, n);
return 0;
}

Output:

C++ Language

Time complexity – O(N^2)

Auxiliary space – O(N)

Python Language

Code:

def calsp(pr, n, S):
   		 S[0] = 1
   		 for a in range(1, n, 1):
   		     S[a] = 1   
   		     b = a - 1
   		     while (b >= 0) and (pr[a] >= pr[b]):
   		         S[a] += 1
   		         b -= 1
def par(arr, n):
    		for a in range(n):
        		print(arr[a], end=" ")
pr = [ 13, 7, 6, 80, 150, 70  ]
n = len(pr)
S = [None] * n
calsp(pr, n, S)
par(S, n)

Output:

Python Language

Time complexity – O(N^2)

Auxiliary space – O(N)

Java Language

Code:

import java.util.Arrays;
class naive 
{
    			static void csp(int pr[], int n, int S[])
    		{
        			S[0] = 1;
        			for (int a = 1; a < n; a++) { S[a] = 1; for (int b = a - 1; (b >= 0) && (pr[a] >= pr[b]); b--)
                		S[a]++;
        		}
   		 }
    			static void par(int arr[])
    		{
        			System.out.print (Arrays.toString(arr));
   		 }
    		public static void main(String[] args)
    		{
        			int pr[] = { 13, 7, 6, 80, 150, 70  };
        			int n = pr.length;
        			int S[] = new int[n];
        			csp(pr, n, S);
        			par(S);
    			}
}

Output:

Java Language

Time complexity – O(N^2)

Auxiliary space – O(N)

Stock Span Problem using Stack

This problem will come with the financial aspect. The consecutive days of the greatest number are given in a stock price that is less than the present price. There are two methods of stock span problem i.e. efficient and inefficient methods. Below is the algorithm of the stock span problem as follows.

Algorithm:

  1. Start
  2. Initialize an empty stack.
  3. After initializing the stack, add the index in the first price of the stack.
  4. Then iterate the I from 0 to n.
    • Then find the greater price of price [i]
    • If the stack is not empty and the price is greater than the peak then pop the st.
    • If stack is empty, set span[i] = i+1
  5. Then return span array.
  6. Stop
C++ Language

Code:

#include <bits/stdc++.h>
using namespace std;
void csp(int pr[], int n, int S[])
{
    			stack sta;
    			sta.push(0);
    			S[0] = 1;
    			for (int a = 1; a < n; a++) {
        			while (!sta.empty() && pr[sta.top()] <= pr[a])
           			 sta.pop();
        			S[a] = (sta.empty()) ? (a + 1) : (a - sta.top());
        			sta.push(a);
    			}
}
void par(int arr[], int n)
{
    			for (int a = 0; a < n; a++)
        			cout << arr[a] << " ";
}
int main()
{
    			int pr[] = { 13, 7, 6, 80, 150, 70 };
    			int n = sizeof(pr) / sizeof(pr[0]);
   	 		int S[n];
    			csp(pr, n, S);
    			par(S, n);
    			return 0;
}

Output:

C++ 2

Time complexity – O(N)

Auxiliary space – O(N)

Java Language

Code:

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class stack {
    		static void cspan(int pr[], int n, int S[])
    		{
        		Deque sta = new ArrayDeque();
        		sta.push(0);
        		S[0] = 1;
        		for (int a = 1; a < n; a++) {
            		while (!sta.isEmpty()
                   		&& pr[sta.peek()] <= pr[a])
                		sta.pop();
            		S[a] = (sta.isEmpty()) ? (a + 1)
                                  : (a - sta.peek());
            			sta.push(a);
        			}
    		}
    		static void par(int arr[])
   		 {
        			System.out.print(Arrays.toString(arr));
   		 }
public static void main(String[] args)
    		{
        			int pr[] = { 10, 4, 5, 90, 120, 80 };
        			int n = pr.length;
        			int S[] = new int[n];
        			cspan(pr, n, S);
        			par(S);
    			}
}

Output:

Stock Span Problem - Java language 2

Time complexity – O(N)

Auxiliary space – O(N)

Python Language

Code:

def cspan(price, S):
   		 n = len(pr)
   		 sta = []
   		 sta.append(0)
   		 S[0] = 1
   		 for a in range(1, n):
   		     while(len(sta) > 0 and pr[sta[-1]] <= pr[a]):
   		         sta.pop()
   		     S[a] = a + 1 if len(sta) == 0 else (a - sta[-1])
   		     sta.append(a)
def par(arr, n):
    		for a in range(0, n):
        		print(arr[a], end=" ")
pr = [10, 4, 5, 90, 120, 80]
S = [0 for i in range(len(pr)+1)]
cspan(pr, S)
par(S, len(pr))

Output:

Stock Span Problem - Python language 2

Time complexity – O(N)

Auxiliary space – O(N)

C Language

Code:

#include 
#define MS 100
int stack[MS], top = -1;
void push(int x)
{
   		 if (top == MS -1) {
   		 printf("Stack OF\n");
    		exit(1);
}
   	 stack[++top] = x;
}
int pop()
{
   	 	if (top == -1)
    	{
        		printf("stack UF");
         		exit(1);
   	 }
    		return stack[top--];
}
int peek()
{
    		return stack[top];
}
int isEmpty()
{
    		return top == -1;
}
void stockspan(int pr[], int n, int sp[])
{
                sp[0] = 1;
                push(0);
    			for (int a = 1; a < n; a++) { while (!isEmpty() && pr[a] >= pr[peek()]) {
        		    pop();
        		}
        			if (isEmpty()) {
        			    sp[a] = a+1;
        		}	 else {
        			 sp[a] = a - peek();
    			}
    			push(a);
}
}
int main()
{
    			int pr[] = { 10, 4, 5, 90, 120, 80 };
    			int n = sizeof(pr) / sizeof(pr[0]);
   	 		    int sp[n];
    			stockspan(pr, n, sp);
    			for (int a = 0; a < n; a++) {
    			    printf("%d", sp[a]);
    			}
    			return 0;
}

Output:

Stock Span Problem - C language 2

Time complexity – O(N)

Auxiliary space – O(N)

Conclusion

The stock span problem is a coding challenge in which we have to find the span of the stock price for the specified day. This is defined as the maximum number of consecutive days before the given day for which the stock price is either lower than or equal to the present day. The stack of the solution decreases the span problem, and it will implement it using the data structure, linked list, and arrays.

Recommended Article

We hope that this EDUCBA information on “Stock Span Problem” was beneficial to you. You can view EDUCBA’s recommended articles for more information,

  1. Introduction to Python
  2. Dictionary Python Remove
  3. Azure Functions Python
  4. Nested Dictionary Python
Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)
  360+ Online Courses |  1500+ Hours |  Verifiable Certificates |  Lifetime Access
4.7
Price

View Course

Related Courses

Oracle DBA Database Management System Training (2 Courses)4.9
SQL Training Program (10 Courses, 8+ Projects)4.8
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more