Home » Interview coding problems/challenges

# Stock Span Problem

**Stock Span Problem**: Here, we are going to **find the solution of Stock Span Problem using Stack and Brute Force Approach** – which has been featured in coding interviews of many top companies such as Goldman sachs, Amazon, Factset, DE-Shaw etc.

Submitted by Divyansh Jaipuriyar, on May 04, 2020

**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 the span of stock's price for all n days.

The span * Si* of the stock's price on a given day

*is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.*

**i**For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.

**Input:**

The first line of input contains an integer * T* denoting the number of test cases. The first line of each test case is

*,*

**N***is the size of the array. The second line of each test case contains*

**N***input*

**N***.*

**arr[i]****Output:**

For each testcase, print the span values for all days.

**Examples:**

Input: T = 1 N = 6 [10, 4, 5, 90, 120, 80] Output: 1 1 2 4 5 1 Input: T = 1 N = 7 [2,4,5,6,7,8,9] Output: 1 2 3 4 5 6 7

**Solution Approach**

**1) Brute Force Approach**

In this approach, we will use the *count* variable for each element and check all the elements before it, if the elements are smaller than or equal to the current element then increase the count variable.

We will store each element's count in a vector and then print the elements.

This approach will traverse the elements in the entire array hence time complexity will **be O(n*n)**.

**Pseudo Code:**

function(arr[],n): //vector to store the elements which are <= to current element. vector<int>v1 //1st element is always 1 as there is no other element v1.push_back(1) for(int i=1;i<n;i++) cnt=1; // Traverse left while the next element // on left is smaller than price[i] for(int j = i - 1; (j >= 0) && (arr[i] >=arr[j]); j--) cnt++; v1.push_back(cnt); for(int i=0;i<n;i++) //print the results. cout<<v1[i]<<" "; return 0;

Time Complexity: O(n*n)

Space Complexity: (n)

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { ll n; //size of stock array variable. cout << "Enter size of stock's price array: "; cin >> n; ll arr[n]; cout << "Enter stock prices: "; for (ll i = 0; i < n; i++) cin >> arr[i]; vector<ll> v1; v1.push_back(1); for (ll i = 1; i < n; i++) { ll cnt = 1; //compare smaller index before current index and check the condition. for (ll j = i - 1; (j >= 0 and arr[j] <= arr[i]); j--) cnt++; v1.push_back(cnt); } cout << "Span Values: "; //print then span values. for (ll i = 0; i < n; i++) cout << v1[i] << " "; cout << "\n"; } return 0; }

**Output**

Enter number of test cases: 3 Enter size of stock's price array: 5 Enter stock prices: 1 2 5 9 2 Span Values: 1 2 3 4 1 Enter size of stock's price array: 9 Enter stock prices: 1 2 3 4 5 6 7 8 9 Span Values: 1 2 3 4 5 6 7 8 9 Enter size of stock's price array: 7 Enter stock prices: 100 99 98 97 96 95 94 Span Values: 1 1 1 1 1 1 1

**2) Stack based solution**

In this approach we will use stack with pair, we will store array element and its index, each time we iterate through array element. We check the previous next greater element, it the previous greater element is found at some location *i*, then we will take the difference between the current index element and the previous greater element.

We will use a vector for each index to push the number of elements that are smaller than or equal to the current element.

We will use a boolean variable *flag*, if the element is pushed according to condition then make variable *flag* true otherwise push 1 as only that element is valid and all element before is greater than it.

**Pseudo Code:**

function(arr[],n): //initialise vector for resulst. vector<int>v1 //initialise stack variable. stack<pair<int,int>>st //put maxm value of int with index -1 if there is no element //is present which are greater than current element //then this will work. st.push({INT_MAX,-1}) for(int i=0;i<n;i++) { //initialse boolean flag variable as false. bool flag=false while(!st.empty()) { //compare with top element of the stack which are before array. if(st.top().first>arr[i]) { v1.push_back(i-st.top().second) flag=true break } else //if current top element is smaller than pop top element. st.pop() } if(flag==false) v1.push_back(1) //push current element and its index. st.push({arr[i],i}) } // print the values of span. for(int i=0;i<n;i++) cout<<v1[i]

Time Complexity for above approach: O(n)

space Complexity for above approach: O(n)

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { ll n; //size of stock array variable. cout << "Enter size of stock's price array: "; cin >> n; ll arr[n]; cout << "Enter stock prices: "; for (ll i = 0; i < n; i++) cin >> arr[i]; stack<pair<ll, ll> > st; //stack declaration. st.push({ INT_MAX, -1 }); vector<ll> v1; for (ll i = 0; i < n; i++) { bool flag = false; while (!st.empty()) { // is stack top is greater than current element then // put the difference value in the vector. if (st.top().first > arr[i]) { v1.push_back(i - st.top().second); flag = true; break; } else st.pop(); //if top value is not greater than pop. } if (flag == false) v1.push_back(1); st.push({ arr[i], i }); } cout << "Span Values: "; //print then span values. for (ll i = 0; i < n; i++) cout << v1[i] << " "; cout << "\n"; } return 0; }

**Output**

Enter number of test cases: 3 Enter size of stock's price array: 5 Enter stock prices: 2 5 9 1 2 Span Values: 1 2 3 1 2 Enter size of stock's price array: 7 Enter stock prices: 100 80 60 70 60 75 85 Span Values: 1 1 1 2 1 4 6 Enter size of stock's price array: 9 Enter stock prices: 1 2 3 4 5 6 7 8 9 Span Values: 1 2 3 4 5 6 7 8 9

Problem reference: https://leetcode.com/problems/online-stock-span/

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.