Given an array arr[] of daily stock prices, the stock span for the i-th day is the count of consecutive days up to and including day i, such that each of those days had a stock price less than or equal to the price on day i.
Examples:
Input: arr[] = [100, 80, 60, 120]
Output: [1, 1, 1, 4]
Explanation: For 100, there are no previous higher prices, so span = 1. For 80 and 60, each is smaller than the previous, so their spans remain 1. For 120, it is greater than all earlier prices (100, 80, 60), so the span extends back across all four days, giving span = 4.
Input: arr[] = [10, 4, 5, 90, 120, 80]
Output: [1, 1, 2, 4, 5, 1]
Explanation: For 10 and 4, no earlier prices are smaller, so span = 1 each. For 5, it is greater than 4, so span = 2. For 90, it is greater than 10, 5, and 4, so span = 4. For 120, it is greater than all previous prices, giving span = 5. Finally, 80 is smaller than 120, so span = 1.
[Naive Approach] Using Nested Loop - O(n2) Time and O(1) Space
The idea is to check, for each day, how many consecutive previous days had stock prices less than or equal to the current day’s price. This can be done by moving leftwards from the current index until a higher price is found or the beginning of the array is reached.
C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> calculateSpan(vector<int>& arr) {
int n = arr.size();
vector<int> span(n, 1);
// Calculate span for each day
for (int i = 1; i < n; i++) {
// Traverse left while the next element
// on the left is smaller than arr[i]
for (int j = i - 1; (j >= 0)
&& (arr[i] >= arr[j]); j--) {
span[i]++;
}
}
return span;
}
int main() {
vector<int> arr = {10, 4, 5, 90, 120, 80};
vector<int> span = calculateSpan(arr);
for (int x : span) {
cout << x << " ";
}
return 0;
}
import java.util.ArrayList;
class GfG {
static ArrayList<Integer> calculateSpan(int[] arr) {
int n = arr.length;
ArrayList<Integer> span = new ArrayList<>();
// Initialize span list with 1s
for (int i = 0; i < n; i++) {
span.add(1);
}
// Calculate span for each day
for (int i = 1; i < n; i++) {
// Traverse left while arr[i] >= arr[j]
for (int j = i - 1; j >= 0
&& arr[i] >= arr[j]; j--) {
span.set(i, span.get(i) + 1);
}
}
return span;
}
public static void main(String[] args) {
int[] arr = {10, 4, 5, 90, 120, 80};
ArrayList<Integer> span = calculateSpan(arr);
for (int x : span) {
System.out.print(x + " ");
}
}
}
def calculateSpan(arr):
n = len(arr)
span = [1] * n
# Calculate span for each day
for i in range(1, n):
# Traverse left while arr[i] >= arr[j]
j = i - 1
while j >= 0 and arr[i] >= arr[j]:
span[i] += 1
j -= 1
return span
if __name__ == "__main__":
arr = [10, 4, 5, 90, 120, 80]
span = calculateSpan(arr)
print(' '.join(map(str, span)))
using System;
using System.Collections.Generic;
class GfG {
static List<int> calculateSpan(int[] arr) {
int n = arr.Length;
List<int> span = new List<int>();
// Initialize span list with 1s
for (int i = 0; i < n; i++) {
span.Add(1);
}
// Calculate span for each day
for (int i = 1; i < n; i++) {
// Traverse left while arr[i] >= arr[j]
for (int j = i - 1; j >= 0
&& arr[i] >= arr[j]; j--) {
span[i]++;
}
}
return span;
}
static void Main() {
int[] arr = { 10, 4, 5, 90, 120, 80 };
List<int> span = calculateSpan(arr);
foreach (int x in span) {
Console.Write(x + " ");
}
}
}
function calculateSpan(arr) {
let n = arr.length;
let span = new Array(n).fill(1);
// Calculate span for each day
for (let i = 1; i < n; i++) {
// Traverse left while arr[i] >= arr[j]
let j = i - 1;
while (j >= 0 && arr[i] >= arr[j]) {
span[i]++;
j--;
}
}
return span;
}
// Driver Code
let arr = [10, 4, 5, 90, 120, 80];
let span = calculateSpan(arr);
console.log(span.join(" "));
[Expected Approach] Using Stack - O(n) Time and O(n) Space
In the previous approach, for each day we kept moving leftward and comparing prices one by one. We continued as long as the current day’s price was greater than or equal to the previous day’s price. But the moment we find a price greater than the current day’s price, we stop.
That means we are always stopping at the first previous greater element.
The idea is to use a stack to directly find this first previous greater element for every day, instead of checking all consecutive smaller ones. Once we know that index, we can compute the span as:
Span[i] = currentIndex − indexOfPreviousGreaterElement
C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> calculateSpan(vector<int>& arr) {
int n = arr.size();
vector<int> span(n);
stack<int> st;
// Process each day's price
for (int i = 0; i < n; i++) {
// Remove elements from the stack while the current
// price is greater than or equal to stack's top price
while (!st.empty() && arr[st.top()] <= arr[i]) {
st.pop();
}
// If stack is empty, all elements to the left are smaller
// Else, top of the stack is the last greater element's index
if (st.empty()) {
span[i] = (i + 1);
}
else {
span[i] = (i - st.top());
}
// Push the current index to the stack
st.push(i);
}
return span;
}
int main() {
vector<int> arr = {10, 4, 5, 90, 120, 80};
vector<int> span = calculateSpan(arr);
for (int x : span) {
cout << x << " ";
}
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
class GfG {
static ArrayList<Integer> calculateSpan(int[] arr) {
int n = arr.length;
ArrayList<Integer> span = new ArrayList<>(
Collections.nCopies(n, 0));
Stack<Integer> st = new Stack<>();
// Process each day's price
for (int i = 0; i < n; i++) {
// Remove elements from the stack while the current price
// is greater than or equal to stack's top price
while (!st.isEmpty() && arr[st.peek()] <=
arr[i]) {
st.pop();
}
// If stack is empty, all elements to the left are smaller
// Else, top of the stack is the last greater element's index
if (st.isEmpty()) {
span.set(i, (i + 1));
} else {
span.set(i, (i - st.peek()));
}
// Push the current index to the stack
st.push(i);
}
return span;
}
public static void main(String[] args) {
int[] arr = {10, 4, 5, 90, 120, 80};
ArrayList<Integer> span = calculateSpan(arr);
for (int x : span) {
System.out.print(x + " ");
}
}
}
def calculateSpan(arr):
n = len(arr)
span = [0] * n
st = []
# Process each day's price
for i in range(n):
# Remove elements from the stack while the current
# price is greater than or equal to stack's top price
while st and arr[st[-1]] <= arr[i]:
st.pop()
# If stack is empty, all elements to the left are smaller
# Else, top of the stack is the last greater element's index
if not st:
span[i] = (i + 1)
else:
span[i] = (i - st[-1])
# Push the current index to the stack
st.append(i)
return span
if __name__ == "__main__":
arr = [10, 4, 5, 90, 120, 80]
span = calculateSpan(arr)
for x in span:
print(x, end=" ")
using System;
using System.Collections.Generic;
class GfG {
static List<int> CalculateSpan(int[] arr) {
int n = arr.Length;
List<int> span = new List<int>(new int[n]);
Stack<int> st = new Stack<int>();
// Process each day's price
for (int i = 0; i < n; i++) {
// Remove elements from the stack while the
// current price is greater than or equal to
// stack's top price
while (st.Count > 0 && arr[st.Peek()]
<= arr[i]) {
st.Pop();
}
// If stack is empty, all elements to the left are smaller
// Else, top of the stack is the last greater element's index
if (st.Count == 0) {
span[i] = (i + 1);
}
else {
span[i] = (i - st.Peek());
}
// Push the current index to the stack
st.Push(i);
}
return span;
}
static void Main(string[] args) {
int[] arr = { 10, 4, 5, 90, 120, 80 };
List<int> span = CalculateSpan(arr);
foreach (int x in span) {
Console.Write(x + " ");
}
}
}
function calculateSpan(arr) {
let n = arr.length;
let span = new Array(n);
let st = [];
// Process each day's price
for (let i = 0; i < n; i++) {
// Remove elements from the stack while the current
// price is greater than or equal to stack's top price
while (st.length > 0
&& arr[st[st.length - 1]] <= arr[i]) {
st.pop();
}
// If stack is empty, all elements to the left are smaller
// Else, top of the stack is the last greater element's index
if (st.length === 0) {
span[i] = (i + 1);
}
else {
span[i] = (i - st[st.length - 1]);
}
// Push the current index to the stack
st.push(i);
}
return span;
}
// Driver Code
let arr = [ 10, 4, 5, 90, 120, 80 ];
let span = calculateSpan(arr);
console.log(span.join(" "));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem