The “Best Time to Buy and Sell Stock” is a frequently asked question in coding interviews, and you can find it on LeetCode here. Although it’s marked as easy, it requires careful consideration to develop an efficient algorithm. In this article, we’ll explore two distinct strategies: the Brute Force approach and the Two Pointers with One Pass algorithm. Let’s start by understanding the problem first.

Problem

You are given an array called prices, where prices[i] represents the cost of a certain stock on day i. Your goal is to maximise profit by selecting one day to buy a stock and a different later day to sell it.

Your task is to calculate the highest possible profit from this single transaction. If no profit can be made, it should return 0.

Examples

Let’s take a look at some examples.

Example 1

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5

The optimal strategy is to buy the stock on day 2 when its price is 1, and then sell it on day 5 when its price has risen to 6. This yields a profit of 6 - 1 = 5. It’s important to note that you cannot buy on day 2 and sell on day 1, as the rules require purchasing before selling.

Example 2

Input: prices = [7, 6, 5, 4, 3, 1]
Output: 0

In this scenario, the stock price decreases each day, meaning there is no opportunity to buy the stock at a lower price and sell it at a higher one later. Therefore, the maximum profit achievable in this case is 0, as no profitable transaction is possible.

Example 3

Input: prices = [7, 3, 6, 1, 2, 3]
Output: 3

The optimal strategy for maximum profit is to buy on day 2 and sell on day 3. It’s important to note that although the lowest buying price occurs on day 4 at 1, there are no subsequent selling opportunities that yield a profit greater than 3.

Now let’s solve this problem starting with the brute force approach.

Brute Force

In this brute force, we will examine every possible pair of buy and sell days to determine the maximum profit with a nested loop. Let’s see the walkthrough first and go through the code.

Brute Force – Walkthrough

We begin by initialising a variable named maxProfit to 0. This variable will serve as a tracker for the highest profit discovered during the process.

The brute force approach employs two nested loops. The outer loop considers each day as a potential buying day, while the inner loop evaluates subsequent days for selling. This setup is essential as it aligns with the rule that the stock must be sold on a day subsequent to the purchase day.

Let’s take a look at the example, [7, 1, 5, 3, 6, 4].

1st outer loop

In the outer loop, our starting point is with the stock priced at 7, treating this as the initial day for buying. We then enter the inner loop to assess the subsequent days for potential selling opportunities, looking for stock values that surpass our buying price of 7. However, as none of the later prices are higher than 7, we advance to the next round of the outer loop.

Current maxProfit = 0

2nd outer loop

We select day 2 as our buying point, with the stock priced at 1. We then use the inner loop to examine the prices on the subsequent days for potential selling opportunities.

1st inner loop

In the first iteration of the inner loop, we focus on day 3, where the stock’s value is 5. Since this is higher than our purchase price of 1, we update the maxProfit by calculating the difference, which is 5 minus 1.

Current maxProfit = 4

2nd inner loop

This time, we sell the stock at a price of 3, which yields a profit of 2. However, since this profit is not greater than our existing maxProfit, we do not update it. This step highlights the critical criteria for updating maxProfit – the generated profit must surpass the maxProfit we’ve previously recorded which tells us that the selling price identified in the inner loop is also higher than the buying price from the outer loop, indicating a profitable transaction.

Current maxProfit = 4

3rd inner Loop

In this iteration, we sell the stock at a price of 6. This results in a profit of 5, which is higher than our current maxProfit. Therefore, we update maxProfit to this new value of 5.

Current maxProfit = 5

4th Inner Loop

This time, the profit stands at 3, which is less than our current maxProfit of 5. Therefore, we bypass any updates to maxProfit.

Current maxProfit = 5

As you might guess, by the end of the outer loop, maxProfit will be 5, which is the value we will return.

Now with the example of [7, 6, 4, 3, 1], as you can see, no day offers a selling price higher than the buying price. Consequently, maxProfit remains unchanged at 0, and that’s the value we’ll return at the end.

With this step-by-step guide in mind, let’s proceed to implement the code.

Brute Force – Implementation in JavaScript

Here is the complete code in JavaScript.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 0; i < prices.length - 1; i++) {
      for (let j = i + 1; j < prices.length; j++) {
        let profit = prices[j] - prices[i];

        if (profit > maxProfit) {
          maxProfit = profit;
        }
      }
    }

    return maxProfit;
  }
}

Implementation steps

1. Create the class and maxProfit method. The method will accept one argument, prices in an array.

class Solution {
  maxProfit(prices) {

  }
}

2. Since we need to keep track of maxProfit, we will start by initialising it. At the end, this value will be returned.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    return maxProfit;
  }
}

3. First, let’s implement the outer loop to designate the buying day. This loop will run from the first day up to the penultimate day. Taking the example of [7, 1, 5, 3, 6, 4], the loop will iterate from index 0 to index 4. The last index is excluded, as we cannot buy on the final day with no subsequent day to sell.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 0; i < prices.length - 1; i++) {

    }

    return maxProfit;
  }
}

4. For each selected buying day from the outer loop, we need to check the potential selling days. To do this, we will create an inner loop. This loop begins from the day following the buying day and continues until the last day.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 0; i < prices.length - 1; i++) {
      for (let j = i + 1; j < prices.length; j++) {
        
      }
    }

    return maxProfit;
  }
}

5. Let’s check the profit by subtracting the price on the buying day from the price on the selling day.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 0; i < prices.length - 1; i++) {
      for (let j = i + 1; j < prices.length; j++) {
        let profit = prices[j] - prices[i];
      }
    }

    return maxProfit;
  }
}

6. Lastly we will compare the calculated profit with our stored maxProfit. If the profit is greater, we’ll update maxProfit to this new value, which will be the final result returned at the end of the algorithm.

class Solution {
  maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 0; i < prices.length - 1; i++) {
      for (let j = i + 1; j < prices.length; j++) {
        let profit = prices[j] - prices[i];

        if (profit > maxProfit) {
          maxProfit = profit;
        }
      }
    }

    return maxProfit;
  }
}

Brute Force - Big O

Time Complexity

The time complexity of the code is O(n²), which means it increases quadratically with the number of items in the list. This happens because the code uses a nested loop to compare each item in the list with every other item. Essentially, if the list has n items, the code performs n x n comparisons. So, as the number of items grows, the time it takes to run the code grows quadratically, specifically at the rate of the square of the number of items.

Space complexity

Regarding the space complexity, it is O(1), indicating that the amount of extra memory or space needed by the code does not increase with the size of the input list. This is because the code only uses a fixed number of variables (like maxProfit, i, j, and profit) which occupy a constant amount of space, regardless of how long the list of prices is. In simpler terms, no matter how many prices we're dealing with, the code always uses the same small amount of extra space.

Two Pointers with One pass

The brute force approach, while straightforward, tends to be inefficient due to its slow time complexity. To enhance performance, let’s employ the two-pointers technique with one-pass algorithm. This approach significantly streamlines the process, offering a more efficient runtime solution. Let's dive into the workings of this approach through a step-by-step walkthrough.

Two Pointers - Walkthrough

With one pass algorithm, we will go through the input data exactly once to get the max profit. Also we are going to use two pointers, buy day and sell day, achieving linear time complexity, O(n). Let’s take a look at the example, [7, 3, 6, 1, 2, 3], with the chart below.

For this approach, we utilise two pointers - one representing the buy day and the other the sell day, and also keep track of the maximum profit. While we iterate through the days, we are ensuring that the sell day remains within the total number of days. Throughout this process, we will assess two primary scenarios:

Whenever the selling price surpasses the buying price, we update the maximum profit to this new value if it is bigger than the currently stored max profit.
If the selling price is the same as or lower than the buying price, we then move the buy day pointer to the sell day pointer.

Let’s talk more on those points.

In the context of the stock market, the goal is to buy low and sell high to maximize profit. When the selling price is equal to or lower than the buying price, it indicates that the current buy day is not the optimal day for purchasing the stock to achieve the maximum profit. By moving the buy day pointer to the current sell day position, the algorithm resets the buy day and starts considering the next day as a potential new selling opportunity, looking for a lower purchase price that could lead to a higher profit when sold later.

Let’s take a look at this example, [7, 3, 6, 1, 2, 3] and go through each iteration.

1st loop

Buy Pointer:	Day 1
Buy Price:	7
Sell Pointer:	Day 2
Sell Price:	3
Current Max Profit:	0

The sell price (3) is less than the buy price (7), meaning no profit can be made. Therefore, we shift the buy pointer to where the sell pointer currently is (Day 2). We’ll also increment the sell pointer to the next day in each iteration to explore new selling opportunities.

2nd loop

Buy Pointer:	Day 2
Buy Price:	3
Sell Pointer:	Day 3
Sell Price:	6
Current Max Profit:	0

The buy day pointer is on day 2 and the sell day pointer is on day 3. Because we can profit, we update the maxProfit to 3, move only sell pointer to day 4.

Updated maxProfit = 3.

3rd loop

Buy Pointer:	Day 2
Buy Price:	3
Sell Pointer:	Day 4
Sell Price:	1
Current Max Profit:	3

The sell price is smaller than buy price, there is no profit we can make. Now we need to move the buy pointer to the sell pointer to find the bigger potential profit as we found smaller buy price. However, one thing to note that finding the smaller buy price doesn’t guarantee to find the max profit. Rather it’s POTENTIALLY giving us an opportunity to search for the bigger profit from the smaller buy price. We will see this happening in the following iterations.

4th loop

Buy Pointer:	Day 4
Buy Price:	1
Sell Pointer:	Day 5
Sell Price:	2
Current Max Profit:	3

Now the sell price is bigger than the buy price but the profit, 1, is not bigger than the current max profit stored, 3, we won’t update the maxProfit value.

5th loop

Buy Pointer:	Day 4
Buy Price:	1
Sell Pointer:	Day 6
Sell Price:	3
Current Max Profit:	3

Same as 4th loop, the profit we make here is not bigger than the current maxProfit, we won’t update it.

End of iteration

We went through all days, and we return the maxProfit.

Two Pointers - Implementation in JavaScript

Here is the complete code in JavaScript.

class Solution {
  maxProfit(prices) {
    let buyDay = 0;
    let sellDay = 1;
    let maxProfit = 0;
  
    while (sellDay < prices.length) {
      if (prices[buyDay] < prices[sellDay]) {
        const profit = prices[sellDay] - prices[buyDay];
        maxProfit = Math.max(maxProfit, profit);
      } else {
        buyDay = sellDay;
      }

      sellDay++;
    }
    
    return maxProfit;
  }
};

Implementation steps

1. Create the class and maxProfit method. The method will accept one argument, prices in array.

class Solution {
  maxProfit(prices) {
    
  }
};

2. Define 3 variables:

buyDay: This is our starting point, set at the first day of the array, which corresponds to index 0.
sellDay: This follows buyDay, positioned at the second day in the array, which is index 1.
maxProfit: This begins at zero and it’s continuously updated as the algorithm runs. Its final value upon completion represents the maximum profit achieved and it will be returned.

class Solution {
  maxProfit(prices) {
    let buyDay = 0;
    let sellDay = 1;
    let maxProfit = 0;
    
    return maxProfit;
  }
};

3. Let’s go through each day to get the maxProfit while the selling day is smaller than the total number of days (meaning as long as the selling day is within the total number of days available). In each iteration, we advance the selling day by one.

class Solution {
  maxProfit(prices) {
    let buyDay = 0;
    let sellDay = 1;
    let maxProfit = 0;

    while (sellDay < prices.length) {
      // price comparison goes here

      sellDay++;
    }
    
    return maxProfit;
  }
};

4. Check whether the current buying price is smaller than the selling price on a given day. If so, there’s an opportunity for profit. We then calculate the profit and update our maxProfit variable, ensuring it holds the higher value between the current iteration’s profit and the previously stored maximum profit. This update is achieved using Math.max.

class Solution {
  maxProfit(prices) {
    let buyDay = 0;
    let sellDay = 1;
    let maxProfit = 0;

    while (sellDay < prices.length) {
      if (prices[buyDay] < prices[sellDay]) {
        const profit = prices[sellDay] - prices[buyDay];
        maxProfit = Math.max(maxProfit, profit);
      } else {
        // logic for non-profitable scenario goes here
      }

      sellDay++;
    }
    
    return maxProfit;
  }
};

5. Finally in scenarios where the buying price is NOT smaller than the selling price, indicating no immediate profit is made, we move the buyDay to the sellDay. This adjustment is crucial for identifying new profitable opportunities in subsequent iterations as discussed in the walkthrough above.

class Solution {
  maxProfit(prices) {
    let buyDay = 0;
    let sellDay = 1;
    let maxProfit = 0;

    while (sellDay < prices.length) {
      if (prices[buyDay] < prices[sellDay]) {
        const profit = prices[sellDay] - prices[buyDay];
        maxProfit = Math.max(maxProfit, profit);
      } else {
        buyDay = sellDay;
      }

      sellDay++;
    }
    
    return maxProfit;
  }
};

Solution in Python

class Solution:
  def maxProfit(self, prices):
    buy_day = 0
    sell_day = 1
    max_profit = 0

    while sell_day < len(prices):
      if prices[buy_day] < prices[sell_day]:
        profit = prices[sell_day] - prices[buy_day]
        max_profit = max(max_profit, profit)
      else:
        buy_day = sell_day

      sell_day += 1

    return max_profit

Two Pointers - Big O

Time complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the prices array since the loop runs once for each element in the prices array.

Space complexity

The space complexity is O(1). This is because the amount of memory used does not increase with the size of the input array. The function only uses a fixed number of variables (buyDay, sellDay, maxProfit and profit), regardless of the input size.