loading...
Cover image for Solving the Best Time to Buy and Sell Stocks Problem in One Pass

Solving the Best Time to Buy and Sell Stocks Problem in One Pass

alisabaj profile image Alisa Bajramovic ・7 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 a very common one: Best Time to Buy and Sell Stock

Say you have an array for which the i-th element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

For example, let's say you were given the array [8, 1, 4, 2, 6, 5] as the input, which is supposed to represent the price of a stock on each day. The best profit you could make would be by buying stock on the second day (index 1), when the price was 1, and selling it on the fifth day (index 4), when the price was 6, for a total max profit of 5 (6 - 1 = 5).

This problem, and variations on it, come up all the time. The first time I saw it, my instinct was to solve it by comparing the values at every price, an approach which would take a long time. However, there's a much more straightforward way to solve this problem, which I'll be discussing in this post.

Approaching the Problem

I think one of the hardest parts of this problem is visualizing it. To help aid that, I'll draw a graph based on a price array of [8, 1, 4, 2, 6, 5].

Graph with y axis of price (goes from 1 to 9) in blue, and x axis of day (goes from 1 to 6) in green. Graph represents the array [8, 1, 4, 2, 6, 5]. At day 1, there is a red dot at price 8, which connects to day 2, where there is a red dot at price 1. That connects to day 3, where there is a red dot at price 4, which connects to day 4, where there is a red dot at price 2. That connects to day 5, where there is a red dot at price 6, which connects to day 6, where there is a red dot at price 5.

The maximum profit is found by finding the smallest number (the lowest valley), which is the price you'd buy the stock at, and then the largest number that comes after it (the tallest peak).

What if, you may be wondering, a small number comes up on a later day, but the maximum profit after that is not very big? For example, let's say the inputted array was [4, 2, 9, 7, 1, 2]. The graph of prices would look like this:

Graph with y axis of price (goes from 1 to 9) in blue, and x axis of day (goes from 1 to 6) in green. Graph represents the array [4, 2, 9, 7, 1, 2]. At day 1, there is a red dot at price 4, which connects to day 2, where there is a red dot at price 2. That connects to day 3, where there is a red dot at price 9, which connects to day 4, where there is a red dot at price 7. That connects to day 5, where there is a red dot at price 1, which connects to day 6, where there is a red dot at price 2.

Even though the price on day 5 is smaller than the price on day 2, the maximum profit would come from buying on day 2 and selling on day 3. In our coded solution, therefore, we should always be looking for a new minimum price, but we also should only update the maximum profit when a new maximum profit is found.

To solve this problem, therefore, we should keep track of the minimum price, and update it only when a smaller price is found. We also should keep track of the profit at every point, which is found by subtracting the minimum price from the current price--if that number is larger than the existing maximum profit, we'll update the maximum profit. Because we will be solving this problem by only walking through the array one time, we'll be doing it in "one pass".

Coding the Solution to the Stock Problem

As we discussed in the approach, we should be keeping track of the minimum price and the maximum profit, which we'll store in variables. We can initialize the minimum price to be the first price in the prices array, and the max profit to be 0. We also know we'll want to return the maximum profit at the end of the function, so we can include the return statement now.

function maxProfit(prices) {
  let minPrice = prices[0];
  let maxProfit = 0;
  //...
  return maxProfit;
}

We'll be solving this problem in one pass, which means we can have a for loop that goes from the start of the prices array to the end.

At each price in the array, we'll want to check if its price is smaller than the current minPrice. If it is, we'll set minPrice to equal the current price we're on, which would be prices[i]

function maxProfit(prices) {
  let minPrice = prices[0];
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    }
    //...
  }
  return maxProfit;
}

The other thing we want to check for is if the difference between the current price and the minimum price is larger than the maximum profit. If it is, we'll want to set maxProfit equal to the difference between prices[i] (the current price) and minPrice (the smallest price we've seen).

function maxProfit(prices) {
  let minPrice = prices[0];
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
      maxProfit = prices[i] - minPrice;
    }
  }
  return maxProfit;
}

This solution solves the algorithm using O(1) space (constant space) and O(n) time (linear time). The reason it's constant space is that the only new variables we're creating store integers--they're not storing entirely new arrays of the size of prices. The reason it's linear time is that we go through every element in the prices array (of size n) to check it, but only go through it once.

Going Through an Example

To see how this algorithm works with an example, we can use the prices array [4, 2, 9, 1, 2].

Graph with y axis of price (goes from 1 to 9) in blue, and x axis of day (goes from 1 to 5) in green. Graph represents the array [4, 2, 9, 1, 2]. At day 1, there is a red dot at price 4, which connects to day 2, where there is a red dot at price 2. That connects to day 3, where there is a red dot at price 9, which connects to day 4, where there is a red dot at price 1. That connects to day 5, where there is a red dot at price 2.

We'll start by setting minPrice equal to prices at 0, which is 4, and maxProfit equal to 0.

First line is the array [4, 2, 9, 1, 2] in black. Second line is `minPrice = prices[0] = 4` in purple. Third line is `maxProfit = 0` in blue.

Now we'll enter the for loop, starting with index 0, 4. 4 is not less than the minimum price, and 4 minus the minimum price is not larger than the maximum profit, so we don't need to update anything.

First line is the array [4, 2, 9, 1, 2] in black, with a bright green circle around `4` at index 0. Second line is `prices[i] < minPrice = 4 < 4` in purple, with a red "X" next to it. Third line is `prices[i] - minPrice > maxProfit = 4 - 4 > 0` in blue, with a red "X" next to it.

Now we're onto index 1, which has a value of 2. This time, 2 is less than the minimum price, so we'll update the minimum price to equal 2.

First line is the array [4, 2, 9, 1, 2] in black, with a bright green circle around `2` at index 1. Second line is `prices[i] < minPrice = 2 < 4` in purple. Third line is `minPrice = prices[i] = 2` in purple.

We're now on index 2, which has a value of 9. 9 is not smaller than the minimum price, so we don't update the minimum price. However, the difference between 9 and the minimum price is larger than the maximum profit, so we can update the maximum profit.

First line is the array [4, 2, 9, 1, 2] in black, with a bright green circle around `9` at index 2. Second line is `prices[i] < minPrice = 9 < 2` in purple, with a red "X" next to it. Third line is `prices[i] - minPrice > maxProfit = 9 - 2 > 0` in blue. Third line is `maxProfit = prices[i] - minPrice = 9 - 2 = 7` in blue.

We're now on index 3, which has a value of 1. 1 is smaller than the minimum price, so we'll update the minimum price.

First line is the array [4, 2, 9, 1, 2] in black, with a bright green circle around `1` at index 3. Second line is `prices[i] < minPrice = 1 < 2` in purple. Third line is `minPrice = prices[i] = 1` in purple.

We're now on the last index, which has a value of 2. 2 is not smaller than the minimum price, so we won't update it. And the difference between 2 and the minimum price is not larger than the existing maximum profit, so we won't update that either.

First line is the array [4, 2, 9, 1, 2] in black, with a bright green circle around `2` at index 4. Second line is `prices[i] < minPrice = 2 < 1` in purple, with a red "X" next to it. Third line is `prices[i] - minPrice > maxProfit = 2 - 1 > 7` in blue, with a red "X" next to it.

Since the for loop is done, we'll return the maximum profit we found, which was 7.

--

Please let me know if you have any questions or other approaches to this problem!

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