Stock Span Problem Using Stack.

The stock span problem is a financial problem where we have a series of daily price quotes for a stock and we need to calculate the span of the stock's price for each day. The span of the stock's price for a particular day is defined as the maximum number of consecutive days (including the current day) for which the stock price is less than or equal to the price of the current day.

Example:

Input: [100, 80, 60, 70, 60, 75, 85]

Output: [1, 1, 1, 2, 1, 4, 6]

Explanation:

• For day 1 (100), the span is 1, as it is the first day.
• For day 2 (80), the span is 1, as the previous day's price (100) is greater.
• For day 3 (60), the span is 1, as the previous day's price (80) is greater.
• For day 4 (70), the span is 2, as the previous day's price (60) is smaller, so we include the day before that (60).
• For day 5 (60), the span is 1, as the previous day's price (70) is greater.
• For day 6 (75), the span is 4, as the previous day's price (60) is smaller, so we include the three days before that (60, 70, 60).
• For day 7 (85), the span is 6, as the previous day's price (75) is smaller, so we include the five days before that (60, 70, 60, 75, 85).

There are many ways to solve this problem, popularly it is solved using stack or dynamic programming and here we are going to discuss all these approaches in detail starting with the brute force approach.

Stock Span Problem Using Brute Force Approach.

In this approach, for each day, we traverse backward and count the number of consecutive days with prices less than or equal to the current day's price. Traverse backward from i-1 to 0 and for each previous day j, compare the stock price at day i with the stock price at day j.

Below is the code implementation of the above approach:

C++ Java Python C#

// Cpp program for stock span problem (brute force)
#include <iostream>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);

    for (int i = 0; i < n; ++i) {
        int spanValue = 1;
         
        //traverse backwards and count the number of consecutive days 
        for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
            spanValue++;
        }

        span[i] = spanValue;
    }

    return span;
}

int main() {
    vector<int> stockPrices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> span = calculateSpan(stockPrices);

    cout << "Stock Prices: ";
    for (int price : stockPrices) {
         cout << price << " ";
    }

    std::cout << "\nSpans: ";
    for (int s : span) {
        std::cout << s << " ";
    }

    return 0;
}

// Java program for stock span problem - brute force approach
import java.util.Arrays;

public class StockSpan {
    public static void main(String[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = calculateSpan(prices);

        System.out.println("Stock Prices: " + Arrays.toString(prices));
        System.out.println("Spans: " + Arrays.toString(span));
    }

    public static int[] calculateSpan(int[] prices) {
        int n = prices.length;
        int[] span = new int[n];
        Arrays.fill(span, 1);

        for (int i = 0; i < n; ++i) {
            int spanValue = 1;
            //traverse backwards and count the number of consecutive days
            for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
                spanValue++;
            }

            span[i] = spanValue;
        }

        return span;
    }
}

# Python program to solve stock span problem
def calculate_span(prices):
n = len(prices)
span = [1] * n

for i in range(1, n):
    span_value = 1

    for j in range(i - 1, -1, -1):
        if prices[j] > prices[i]:
            break
        span_value += 1

    span[i] = span_value

return span

stock_prices = [100, 80, 60, 70, 60, 75, 85]
span = calculate_span(stock_prices)

print("Stock Prices: " + str(stock_prices))
print("Spans: " + str(span))

// C# code to solve stock span problem - brute force
using System;

class StockSpan {
    public static void Main() {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = CalculateSpan(prices);

        Console.WriteLine("Stock Prices: " + string.Join(" ", prices));
        Console.WriteLine("Spans: " + string.Join(" ", span));
    }

    public static int[] CalculateSpan(int[] prices) {
        int n = prices.Length;
        int[] span = new int[n];
        Array.Fill(span, 1);

        for (int i = 0; i < n; ++i) {
            int spanValue = 1;

            for (int j = i - 1; j >= 0 && prices[j] <= prices[i]; --j) {
                spanValue++;
            }

            span[i] = spanValue;
        }

        return span;
    }
}

Output:

Stock Prices: 100 80 60 70 60 75 85 
Spans: 1 1 1 2 1 4 6 

Time Complexity: O(n^2).

Space Complexity: O(1).

Stock Span Problem Using Stack.

In this approach, we utilize a stack to efficiently calculate the span of stock prices. We traverse the array of stock prices once and maintain a stack of previous days' indices along with their corresponding span values. Below are the algorithm steps that you follow for better understanding.

Algorithm Steps:

• Create an empty stack to store indices.
• Initialize an array span of the same size as the number of days, initially filled with zeros. This array will store the span for each day.
• Iterate through each day, starting from the first day.
• -- While the stack is not empty and the price of the stock on the current day is greater than the price on the day represented by the index at the top of the stack: Pop the index from the stack.
• -- If the stack is empty, set the span for the current day as the current day itself; otherwise, set it as the difference between the current day and the day represented by the index at the top of the stack.
• -- Push the current day's index onto the stack.
• After completing the iteration, the span array contains the span for each day.

Below is the code implementation for the above approach:

C++ Java Python C#

// Stock span problem using stack
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> calculateSpan(const vector<int>& prices) {
    stack<int> st;
    vector<int> span(prices.size(), 0);

    for (int i = 0; i < prices.size(); ++i) {
        while (!st.empty() && prices[i] >= prices[st.top()]) {
            st.pop();
        }

        span[i] = st.empty() ? i + 1 : i - st.top();
        st.push(i);
    }

    return span;
}

int main() {
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    vector<int> span = calculateSpan(prices);

    cout << "Stock Prices: ";
    for (int price : prices) {
        cout << price << " ";
    }

    cout << "\nStock Spans: ";
    for (int s : span) {
        cout << s << " ";
    }

    return 0;
}

// Stock Span Problem Using Stack
import java.util.Stack;
import java.util.Arrays;

public class StockSpan {
    public static void main(String[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = calculateSpan(prices);

        System.out.println("Stock Prices: " + Arrays.toString(prices));
        System.out.println("Stock Spans: " + Arrays.toString(span));
    }

    public static int[] calculateSpan(int[] prices) {
        Stack<Integer> st = new Stack<>();
        int[] span = new int[prices.length];

        for (int i = 0; i < prices.length; i++) {
            while (!st.isEmpty() && prices[i] >= prices[st.peek()]) {
                st.pop();
            }

            span[i] = st.isEmpty() ? i + 1 : i - st.peek();
            st.push(i);
        }

        return span;
    }
}

# Python code for stock span problem using stack
def calculate_span(prices):
stack = []
span = [0] * len(prices)

for i in range(len(prices)):
    while stack and prices[i] >= prices[stack[-1]]:
        stack.pop()

    span[i] = len(stack) if not stack else i - stack[-1]
    stack.append(i)

return span

prices = [100, 80, 60, 70, 60, 75, 85]
span = calculate_span(prices)

print("Stock Prices: " + str(prices))
print("Stock Spans: " + str(span))

// C# code for stock span problem using stack
using System;
using System.Collections.Generic;

public class StockSpan {
    public static void Main(string[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] span = CalculateSpan(prices);

        Console.WriteLine("Stock Prices: " + string.Join(" ", prices));
        Console.WriteLine("Stock Spans: " + string.Join(" ", span));
    }

    public static int[] CalculateSpan(int[] prices) {
        Stack<int> st = new Stack<int>();
        int[] span = new int[prices.Length];

        for (int i = 0; i < prices.Length; i++) {
            while (st.Count > 0 && prices[i] >= prices[st.Peek()]) {
                st.Pop();
            }

            span[i] = st.Count == 0 ? i + 1 : i - st.Peek();
            st.Push(i);
        }

        return span;
    }
}

Output:

Stock Prices: 100 80 60 70 60 75 85 
Spans: 1 1 1 2 1 4 6 

Time Complexity: O(n).

Space Complexity: O(n).

There are many other approaches as well to solve this problem like by using Dynamic Programming and Monitonic Stack that we have covered separately in other articles.

Next Greater Element (NGE) for Every Element of Array.

Given an array nums[] of distinct integers, find the next greater element for each element in the array. The next greater element is the first greater element to its right. If no such element exists, consider it as -1. Write a function to return an array containing the next greater elements in the input array.

Example:

Input: [3, 1, 4, 2]

Output: [4, 4, -1, -1]

Explanation:

- For element 3, the next greater element is 4.

- For element 1, the next greater element is 4.

- For element 4, there is no next greater element to its right, so it is -1.

- For element 2, there is no next greater element to its right, so it is -1.

Input: [4, 5, 2, 10, 8]

Output: [5, 10, 10, -1, -1]

Explanation:

- For element 4, the next greater element is 5.

- For element 5, the next greater element is 10.

- For element 2, the next greater element is 10.

- For element 10, there is no next greater element to its right, so it is -1.

- For element 8, there is no next greater element to its right, so it is -1.

This is one of the popular stack-based problems that has been asked in many interviews and here we will understand how to approach this problem starting with a brute force solution and then optimizing it using the stack data structure.

There are multiple ways of asking this same question in an interview and if you understand the solution to this one question I can guarantee that you will be able to solve the other similar kind of questions. These questions are:

• Next Greater Element to its right.
• Next Smaller Element to its right.
• Next Greater Element to its left.
• Next Smaller Element to its left.

Brute Force Approach to Find NGE to Right.

The brute force approach is quite simple for this question, using two nested loops. The outer loop will traverse the given input array and the inner will find the next greater element to the right side of the current index. 

Algorithm Steps:

• Iterate through each element in the array.
• For each element, iterate through the elements to its right.
• Find the first element greater than the current element.
• If found, set it as the next greater element. If not found, set it as -1.
• Continue this process for each element in the array.

Below is the code implementation of the above approach:

C++ Java Python C#

// CPP program to find next greater element
#include<iostream>
#include<vector>
using namespace std;

// function to find next greater element
vector<int> nextGreaterElement(vector<int> nums) {
    int n = nums.size();
    vector<int> result(n, -1);

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++){
            if(nums[j] > nums[i]){
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}
int main() {
    vector<int> nums = {4, 5, 2, 10, 8};

    vector<int> result = nextGreaterElement(nums);

    cout << "Input Array: ";
    for(int num:nums){
        cout << num << " ";
    }

    cout << "\nNext Greater Elements to Right: ";
    for(int num:result){
        cout << num << " ";
    }

    return 0;
}

// Java code to find next greater element
import java.util.Arrays;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    result[i] = nums[j];
                    break;
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = nextGreaterElement(nums);

        System.out.print("Input Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }

        System.out.println("\nNext Greater Elements to Right: " + Arrays.toString(result));
    }
}

# Python code to find next greater element
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n

for i in range(n):
    for j in range(i + 1, n):
        if nums[j] > nums[i]:
            result[i] = nums[j]
            break

return result

nums = [4, 5, 2, 10, 8]
result = nextGreaterElement(nums)

print("Input Array:", nums)
print("Next Greater Elements to Right:", result)

// C# code to find next greater element
using System;

class Program {
    static int[] NextGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i]) {
                    result[i] = nums[j];
                    break;
                }
            }
        }
        return result;
    }

    static void Main() {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = NextGreaterElement(nums);

        Console.Write("Input Array: ");
        foreach (int num in nums) {
            Console.Write(num + " ");
        }

        Console.WriteLine("\nNext Greater Elements to Right: " + string.Join(" ", result));
    }
}

Output:

Input Array: 4 5 2 10 8 
Next Greater Elements to Right: 5 10 10 -1 -1

• Time Complexity: O(n^2) as we have used two nested loops to solve this problem.
• Space Complexity: O(1) we have not used any extra space. 

Next Greater Element Using Stack.

The efficient way of solving this problem is by using a stack data structure. The stack helps keep track of potential candidates for the next greater element. Let's follow the algorithm steps given below to understand this approach in detail.

Algorithm Steps:

• Initialize an empty stack to store indices of elements.
• Create an array to store the result.
• Iterate through the array from right to left.
• -- If the stack is empty, set the result at index i to -1.
• -- If the stack is not empty and the top element of the stack is greater than nums[i], then the top element is the next greater element, so update the result array at index i with the stack top.
• -- If the stack is not empty and the top element of the stack is less than or equal to nums[i], pop elements from the stack until finding an element greater than nums[i]. Update the result array at index i with the stack top (if any).
• -- Push the current element nums[i] onto the stack.
• The resulting array now contains the next greater elements to the right for each element.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code to find next greater element using stack
#include <iostream>
#include <vector>
#include <stack>
#include<algorithm>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    stack<int> st;

    for (int i = n - 1; i >= 0; i--) {
        // stack is empty means no next greater element present
        if(st.size() == 0) {
            result[i] = -1;
        } else if(st.size() > 0 && st.top() > nums[i]) {
            result[i] = st.top();
        } else if(st.size() > 0 && st.top() <= nums[i]) {
            //pop the stack element until you find next greater
            while(st.size() > 0 && st.top() <= nums[i]){
                st.pop();
            }
            if(st.size() == 0) {
                result[i] = -1;
            } else {
                result[i] = st.top();
            }
        }
        st.push(nums[i]);
    }

    return result;
}

int main() {
    vector<int> nums = {4, 5, 2, 10, 8};
    vector<int> result = nextGreaterElement(nums);

    cout << "Input Array: ";
    for (int num : nums) {
        cout << num << " ";
    }
    
    cout << "\nNext Greater Elements to Right: ";
    for (int num : result) {
        cout << num << " ";
    }

    return 0;
}

// Java code to find the next greater element using stack
import java.util.Stack;
import java.util.Arrays;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            if (stack.isEmpty()) {
                result[i] = -1;
            } else if (stack.peek() > nums[i]) {
                result[i] = stack.peek();
            } else {
                while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                    stack.pop();
                }
                result[i] = stack.isEmpty() ? -1 : stack.peek();
            }
            stack.push(nums[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 2, 10, 8};
        int[] result = nextGreaterElement(nums);

        System.out.print("Input Array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }

        System.out.println("\nNext Greater Elements to Right: " + Arrays.toString(result));
    }
}

# Python code to find the next greater element using stack
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = []

for i in range(n - 1, -1, -1):
    if not stack:
        result[i] = -1
    elif stack[-1] > nums[i]:
        result[i] = stack[-1]
    else:
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        result[i] = stack[-1] if stack else -1
    stack.append(nums[i])

return result

nums = [4, 5, 2, 10, 8]
result = next_greater_element(nums)
print(f"Input Array: {nums}")
print(f"Next Greater Elements to Right: {result}")

// C# code to find the next greater element using stack
using System;
using System.Collections.Generic;

class NextGreaterElement
{
    static int[] NextGreaterElementToRight(int[] nums)
    {
        int n = nums.Length;
        int[] result = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = n - 1; i >= 0; i--)
        {
            if (stack.Count == 0)
            {
                result[i] = -1;
            }
            else if (stack.Peek() > nums[i])
            {
                result[i] = stack.Peek();
            }
            else
            {
                while (stack.Count > 0 && stack.Peek() <= nums[i])
                {
                    stack.Pop();
                }
                result[i] = (stack.Count == 0) ? -1 : stack.Peek();
            }
            stack.Push(nums[i]);
        }

        return result;
    }

    static void Main()
    {
        int[] nums = { 4, 5, 2, 10, 8 };
        int[] result = NextGreaterElementToRight(nums);

        Console.Write("Input Array: ");
        foreach (int num in nums)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine("\nNext Greater Elements to Right: " + "[" + string.Join(", ", result) + "]");
    }
}

Output:

Input Array: 4 5 2 10 8 
Next Greater Elements to Right: 5 10 10 -1 -1

• Time Complexity: The time complexity of finding the next greater element using stack is O(n) because the next greater element is found on top of the stack
• Space Complexity: As we are using a stack to store the elements while traversing so space complexity will be O(n).