- Problem Statement<\/a><\/li>
- Brute Force Approach<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Approach 2: Stack<\/a><\/li>
- C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul>
- FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given a list of prices of a stock for N<\/strong> days. The task is to find the stack span for each day.
Stock span<\/strong> can be defined as the number of consecutive days before the current day where the price of the stack was equal to or less than the current price.<\/p>\n\n\n\n<\/figure>\n\n\n\n
Examples:<\/strong><\/p>\n\n\n\n
Input: A[] <\/strong>= [100,60,70,65,80,85]
Output:<\/strong> [1,1,2,1,4,5]
Explanation: <\/strong>Explained in image above.<\/p>\n\n\n\nInput: <\/strong>[31, 27, 14, 21, 30, 22]
Output: <\/strong>[1, 1, 1, 2, 4, 1]\n\n\n\nBrute Force Approach<\/h2>\n\n\n\n
A simple approach to solve this problem is to run two nested loops<\/strong> and for each element, find the maximum length such that all consecutive elements are smaller than the current element.
In case a large element is found, terminate the loop.<\/p>\n\n\n\nC++ Code<\/h3>\n\n\n\n
void calculateSpan(int price[], int n, int S[]) {\n S[0] = 1;\n for (int i = 1; i < n; i++) {\n S[i] = 1;\n for (int j = i - 1;\n (j >= 0) &&\n (price[i] >= price[j]); j--)\n S[i]++;\n }\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
static void calculateSpan(int price[], int n, int S[]) {\n S[0] = 1;\n for (int i = 1; i < n; i++) {\n S[i] = 1;\n for (int j = i - 1;\n (j >= 0) && (price[i] >= price[j]); j--)\n S[i]++;\n }\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
def calculateSpan(price, n, S):\n S[0] = 1\n for i in range(1, n, 1):\n S[i] = 1\n j = i - 1\n while (j>= 0) and (price[i] >= price[j]) :\n S[i] += 1\n j -= 1<\/pre>\n\n\n\n
Time Complexity:<\/strong>O(N^2), where N is total size of the array
Space Complexity:<\/strong>O(1), as no extra space is used<\/p>\n\n\n\nApproach 2: Stack<\/h2>\n\n\n\n
Instead of traversing through all previous elements of the current element, we can use the Stack<\/strong> data structure which can solve the problem in linear time.
The approach of this problem is very similar to Next Greater Element. <\/strong>But, the indices of the next greater element is stored instead of the element itself.<\/p>\n\n\n\nAlgorithm<\/strong><\/p>\n\n\n\n
- Initialise an array S[0] = 1<\/strong> for day 0.<\/li>
- Initialise a stack and push the index<\/strong> of the first day into the stack.<\/li>
- Traverse a loop from 1<\/strong> to N<\/strong> and for each iteration, do the following:
- If the stack is not empty<\/strong> and price <\/strong>of current element is greater than the top of stack, pop the element.<\/li>
- Else if, stack is not empty then, subtract index from S[i]<\/strong>, i.e. S[i] = i – S.top()<\/strong>.<\/li>
- Else, S[i] =\u00a0 i + 1<\/strong><\/li><\/ul><\/li>
- Push the current index i<\/strong> into the stack.<\/li><\/ul>\n\n\n\n
C++ Implementation<\/h3>\n\n\n\n
void calculateSpan(int price[], int n, int S[]) {\n stack < int > st;\n st.push(0);\n S[0] = 1;\n for (int i = 1; i < n; i++) {\n while (!st.empty() && price[st.top()] < price[i])\n st.pop();\n \n S[i] = (st.empty()) ? (i + 1) : (i - st.top());\n st.push(i);\n }\n}<\/pre>\n\n\n\nJava Implementation<\/h3>\n\n\n\n
static void calculateSpan(int price[], int n, int S[]) {\n Stack < Integer > st = new Stack < > ();\n st.push(0);\n \n S[0] = 1;\n for (int i = 1; i < n; i++) {\n while (!st.empty() && price[st.peek()] <= price[i])\n st.pop();\n \n S[i] = (st.empty()) ? (i + 1) : (i - st.peek());\n st.push(i);\n }\n}<\/pre>\n\n\n\nPython Implementation<\/h3>\n\n\n\n
def calculateSpan(price, S):\n \n n = len(price)\n st = []\n st.append(0)\n \n S[0] = 1\n \n for i in range(1, n):\n while( len(st) > 0 and price[st[-1]] <= price[i]):\n st.pop()\n \n S[i] = i + 1 if len(st) <= 0 else (i - st[-1])\n \n st.append(i)<\/pre>\n\n\n\n
- Else if, stack is not empty then, subtract index from S[i]<\/strong>, i.e. S[i] = i – S.top()<\/strong>.<\/li>
- Initialise a stack and push the index<\/strong> of the first day into the stack.<\/li>
- Java Implementation<\/a><\/li>
- Java Code<\/a><\/li>
- Brute Force Approach<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-5-1024x631.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-3-2-1024x584.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-6-1024x631.png\")
<\/figure>\n\n\n\n