loading...

The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen

alisabaj profile image Alisa Bajramovic Updated on ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm is the stock span problem: write a class called StockSpanner which takes in daily price quotes, and returns the 'span' of that stock's price. The 'span' is the number of consecutive days (including today) that the current price is equal to or less than today's stock.

For example -- let's say the price of stocks over five days was: [100, 80, 60, 70, 80]. The span is [1, 1, 1, 2, 4] (note: every day will at least have a span of 1).

This is a tricky problem, and there are many ways to approach it. The way I ended up tackling it was by using a stack, which would keep track of the highest price seen, and its span so far.

Stacks

In case you need a refresher, a stack is a list in which we always access the last element put in. Picture it like a stack of dishes in the sink: you keep piling dishes on top of each other, and when you're finally ready to wash them, you have to start by washing the topmost dish. Stacks are different from queues in this way (with queues, the first thing that goes in is the first thing that comes out).

The reason that stacks are useful in this kind of problem is because we're concerned with the question of "what was the most recent highest number we've seen?" We don't need to check every number that came before the current one--that would be way too inefficient, and our stack could be thousands of elements long. Instead, we can just compare elements as we see them.

With that, we can start approaching the problem (the Leetcode for which can be found here).

The Code

The problem is asking for us to build a class, which will have a function called "next", which will take in a new price. Also, as I talked about above, I wanted to approach this problem by building a stack, so that should be initialized in the constructor. So, we can begin by writing out the basics of the code.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    //...
  }
}

Now, we know from the problem that we need to keep track of the span, and the span is always going to be at least 1. So, every time we get a new price, we can create a variable called span, and set it equal to 1.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    let span = 1
    //...
  }
}

The next thing to do is to check if the top element in the stack has a price that's less than the current element. To do that, we're going to have some conditionals, as well as a while loop. But, before we get to that point, we need to think about the case when there's no elements in the stack at all. We'll need to push something to the stack. For this problem, we should push an array containing the price and span of the current element.

An array is useful here because there are only two elements that we're working with, so it's easy to remember what's in the 0th index and what's in the 1st index. If we were working with more variables, it may be helpful to use a hash with key-value pairs.

Also, we know that we're going to be returning the span every time a new element is added, so we can just go ahead and add a line to return the span here.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    let span = 1
    //...

    this.stack.push([price, span])
    return span
  }
}

Now comes the comparisons. What we're checking for is if the current element has a price that's greater than or equal to the price of the topmost element in the stack. We can access the topmost element by doing this.stack[this.stack.length-1]. Since we know each element in this.stack is an array of [price, span], we can access the price of the topmost element in the stack with this.stack[this.stack.length-1][0], since price is at the 0 index.

Because the new element could be larger than a number of the previous prices, this is a good place to use a while loop. That way, we can keep on checking the topmost element of the stack, and removing them if their price is less than the new element's price.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    let span = 1
    while (this.stack[this.stack.length - 1][0] <= price) {
      //...
    }
    this.stack.push([price, span])
    return span
  }
}

Inside the while loop is where we will pop off the topmost element of the stack. However, before we do that, we need to know what the span of the topmost element was. We do this because, if the new price is greater than the top element of the stack, then the new price's span will at least be 1 + the last highest one's span. This is a good time to use .pop(), which returns the removed element. Since we only want the span of the removed element from the stack, we can specify that, and store it in a new variable called lastSpan. We can add lastSpan to the span of the current element.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    let span = 1
    while (this.stack[this.stack.length - 1][0] <= price) {
      let lastSpan = this.stack.pop()[1]
      span += lastSpan
    }
    this.stack.push([price, span])
    return span
  }
}

We're almost done! The only other thing we need to add has to do with edge cases. Let's say there are no elements in the stack, either because we just created a new instance of the class, or we've popped off all of the smaller prices already. The while loop, as written, while throw an error, since it can't compare 'price' to the last element in the stack, if there is nothing in the stack to compare it to. Therefore, that loop should also check that the stack has something in it to compare against.

class StockSpanner {
  constructor() {
    this.stack = []
  }

  next(price) {
    let span = 1
    while (this.stack.length >= && this.stack[this.stack.length - 1][0] <= price) {
      let lastSpan = this.stack.pop()[1]
      span += lastSpan
    }
    this.stack.push([price, span])
    return span
  }
}

With that simple check, if there's nothing in the stack to begin with, then the function will skip over the while loop altogether, and just move onto pushing the price and span into the stack.

I know this was a trickier problem, so please feel free to ask clarifying questions if you have any in the comments.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide