Stock Span Problem

Question

The Stock Span problem is commonly asked in Core Companies interviews (like Google, Amazon,Yahoo) and taught as the application of the stack data structure in universities. Let’s take a look at the problem statement:

For example, {100,60,70,65,80,85} span will be {1,1,2,1,4,5}.

Answer 1

We can solve this problem in two ways-

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

Method 1- Brute-force approach (using nested loops)-

In this method, two loops will be used. The outer loop will iterate over all the array elements and the inner loop will iterate over all the next elements of currently pointed by outer loop. The inner loop will be terminated if any greater element will be found and if the greater element is not found then -1 will be added as result.

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]))

Output:

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

Time Complexity: O(n^2).

Method 2- Using Stack

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))

Output:

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

Time Complexity: O(n).