Stock span problem

Category: Data Structures
Tags: #datastructures#stack

Stock span problem is a financial problem mostly asked in interviews and its optimized solution can be obtained using stack. Here is the solution of stock span problem with explanation using stack and brute force approach.

Stock span problem

Problem

The stock span problem is a type of financial problem based on stocks where daily price of a stock is given.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

Stock span problem example

Example -

Input: [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]

Input: [31, 27, 14, 21, 30, 22]
Output: [1, 1, 1, 2, 4, 1]

We will see two ways to solve the problems

  1. Brute-force approach (using nested loops)
  2. Using stack

Brute-force approach (using nested loops)

In this approach we will use two loops. Outer loop will iterate over all the array items and inner loop will iterate over all the previous elements of currently pointed by outer loop. Inner loop will check, if any greater element will be found then loop will be terminated.

Python
def stock_span(arr):
    result = []
    for i in range(len(arr)):
        flag = True
        count = 0
        for j in range(i, -1, -1):
            if arr[j] <= arr[i]:
                count += 1
            else:
                flag = False
                break
        
        if not flag or j <= 0:
            result.append(count)

    return result

print(stock_span([100, 80, 60, 70, 60, 75, 85]))
JavaScript
function stockSpan(arr) {
    const result = [];
    for (var i = 0; i < arr.length; i++) {
        var flag = true;
        var count = 0;
        for (var j = i; j >= 0; j--) {
            if (arr[j] <= arr[i]) {
                count++;
            }
            else {
                flag = false;
                break;
            }
        }
        if (!flag || j <= 0)
            result.push(count);
    }
    return result;
}

console.log(stockSpan([100, 80, 60, 70, 60, 75, 85]));

Output

[1, 1, 1, 2, 1, 4, 6]

Although, we have solved this problem using loops but this is not an optimized solution. Because time complexity of this solution is O(n^2).

Using stack

You can observe that this problem is very much similar to Nearest greater element to left because in this problem we are trying to find the nearest greater element to left.

But instead of the greater element, we are storing the index of greater element and then we will subtract index of greater from the index of current element.

Stock span problem using stack

Program

Python
class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, num):
        self.stack.append(num)

    def pop(self):
        if self.isEmpty():
            raise Exception('Stack Underflow')
        return self.stack.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.stack[-1]

def stock_span(arr):
    stack = Stack()
    result = []

    for i in range(0, len(arr)):
        if stack.isEmpty():
            result.append(-1)
            stack.push([arr[i], i])
        elif not stack.isEmpty():
            while not stack.isEmpty() and arr[i] > stack.peek()[0]:
                stack.pop()
            if stack.isEmpty():
                result.append(-1)
            else:
                result.append(stack.peek()[1])
            stack.push([arr[i], i])

    output = []
    for index, elem in enumerate(result):
        output.append(index - elem)

    return output

arr = [100, 80, 60, 70, 60, 75, 85]
print(stock_span(arr))
JavaScript
class Stack {
    constructor() {
        this.stack = [];
    }
    
    isEmpty() {
        return this.stack.length === 0;
    }
    
    push(num) {
        this.stack.push(num);
    }
    
    pop() {
        if (this.isEmpty())
            throw 'Stack underflow';
        return this.stack.pop();
    }
    
    peek() {
        if (this.isEmpty())
            return null;
        return this.stack[this.stack.length - 1];
    }
}

function stockSpan(arr) {
    const stack = new Stack();
    const result = [];
    
    for (let i = 0; i < arr.length; i++) {
        if (stack.isEmpty()) {
            result.push(-1);
            stack.push([arr[i], i])
        } else if (!stack.isEmpty()) {
            while (!stack.isEmpty() && arr[i] > stack.peek()[0]) {
                stack.pop();
            }
            if (stack.isEmpty())
                result.push(-1);
            else
                result.push(stack.peek()[1]);
            stack.push([arr[i], [i]]);
        }
    }
    
    const output = [];
    for (let i = 0; i < result.length; i++)
        output.push(i - result[i]);
    
    return output;
}

const arr = [100, 80, 60, 70, 60, 75, 85];
console.log(stockSpan(arr));

Output

[1, 1, 1, 2, 1, 4, 6]