This is the most famous problem asked in the Coding Rounds of many companies like Flipkart, Adobe, Microsoft, etc. In Stock Span Problem you have to find the consecutive smaller or equal before it in an array.
To implement this logic we use Stack an abstract data type to store the Index and Data. It is the variation of the Nearest Greater Left in the Stack.
Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?
Steps to Solve the Problem
- Create a stack s of type int and push 0 in it
- Set the answer of day 1 as 1 and run a for loop to traverse the days
- While the stack is not empty and the price of s.top is less than or equal to the price of the current day, pop out the top value
- Set the answer of the current day as i+1 if the stack is empty else equal to i – s.top
- Push the current day into the stack
- Print the answer using the answer array
Solution in C++
#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void printNGE(int arr[], int n)
{
stack<pair<int, int> > s;
vector<int> v;
for (int i=0;i<n;i++){
if(s.size()==0){
v.push_back(-1);
}
else if (s.size()>0 && s.top().first>arr[i]){
v.push_back(s.top().second);
}
else if(s.size()>0 && s.top().first<=arr[i]){
while(s.size()>0 && s.top().first<=arr[i]){
s.pop();
}
if(s.size()==0){
v.push_back(-1);
}
else
{ v.push_back(s.top().second);
}
}
s.push({arr[i], i});
};
//reverse(v.begin(), v.end());
for (int i = 0; i < n; i++) {
v[i] = i - v[i];
cout << v[i] <<endl;
}
}
int main()
{
int arr[] = {100,80,60,70,60,75,85};
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
/// contributed by Iresh SinglaOutput
1
1
1
2
1
4
6
Solution in Python
from typing import List
from collections import deque
def printNGE(arr: List[int], n: int) -> None:
s = deque()
v = []
for i in range(n):
if not s:
v.append(-1)
elif s and s[-1][0] > arr[i]:
v.append(s[-1][1])
elif s and s[-1][0] <= arr[i]:
while s and s[-1][0] <= arr[i]:
s.pop()
if not s:
v.append(-1)
else:
v.append(s[-1][1])
s.append((arr[i], i))
for i in range(n):
v[i] = i - v[i]
print(v[i])
arr = [100,80,60,70,60,75,85]
n = len(arr)
printNGE(arr, n)
Output
1 1 1 2 1 4 6
Solution in Java
import java.util.*;
public class Main {
public static void printNGE(int[] arr, int n) {
Stack<Pair<Integer, Integer>> s = new Stack<>();
List<Integer> v = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (s.empty()) {
v.add(-1);
} else if (!s.empty() && s.peek().getKey() > arr[i]) {
v.add(s.peek().getValue());
} else if (!s.empty() && s.peek().getKey() <= arr[i]) {
while (!s.empty() && s.peek().getKey() <= arr[i]) {
s.pop();
}
if (s.empty()) {
v.add(-1);
} else {
v.add(s.peek().getValue());
}
}
s.push(new Pair<Integer, Integer>(arr[i], i));
}
for (int i = 0; i < n; i++) {
v.set(i, i - v.get(i));
System.out.println(v.get(i));
}
}
public static void main(String[] args) {
int[] arr = { 100, 80, 60, 70, 60, 75, 85 };
int n = arr.length;
printNGE(arr, n);
}
}
Output
1 1 1 2 1 4 6
Time Complexity: O(N). It seems more than O(N) at first look. If we take a closer look, we can observe that every element of the array is added and removed from the stack at most once.
Auxiliary Space: O(N) in the worst case when all elements are sorted in decreasing order.