Best Time to Buy and Sell Stock Problem (with code)

 

In the context of data structures and algorithms, the issue of when to buy and sell stocks for Profit maximization in stock trading can be framed as a problem. The “Best Time to Buy and Sell Stock” problem is the name given to this issue, which can be solved with the help of algorithms like greedy or dynamic programming. In this article, we will understand the problem and explore various approaches to solve it from the naive brute-force method to more optimized techniques using sorting and two-pointers.

Best Time to Buy and Sell Stock Problem

In the Best Time to Buy and Sell a Stock problem, you are given an array of prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Let’s understand it with an example:

Input: 

prices = [8,1,2,4,7,3]

Output:

6

In this example, buying on day 2 (price = 1) and selling on day 5 (price = 7) results in the maximum profit of 7 – 1 = 6.

Brute Force: Recursive Approach

A brute-force approach to tackling the best time to buy and sell stocks problem involves using recursion to check all possibilities. In this strategy, a recursive function is designed to compute the maximum profit for a specific index while taking into account the decision to either buy or sell stocks at that position. 

The problem is deconstructed into smaller subproblems by exploring the options of buying and selling stocks at each index. 

Here’s a simple explanation of the brute-force approach for this problem:

• Define Subproblems: Identify the subproblem that needs to be solved. In this case, the subproblem is finding the maximum profit that can be obtained up to each day.
  
• Formulate Recurrence Relation: Express the solution to the original problem in terms of solutions to its subproblems. For each day i, the maximum profit up to that day can be calculated by considering the minimum stock price encountered so far and the current stock price.

This methodology aims to exhaustively examine all the possibilities and therefore it has the time complexity of O(n^2) and is not efficient for large inputs.

Dynamic Programming Approach

The dynamic programming approach is an optimized version of the recursion approach. It uses a 2D dynamic programming table to store the results of subproblems. 

The table has two dimensions: the index of the prices array and a boolean flag indicating whether we can sell stocks at that index. By iteratively filling up the table, we can find the maximum profit by considering the choices of buying and selling stocks at each index. 

We need to add up the following things in brute force approach implementing dynamic programming technique :

• Create a Table (Memoization): Use a table to store the solutions to subproblems. The table is often referred to as a memoization table. Each entry in the table corresponds to the solution of a subproblem. In this case, the table can store the maximum profit that can be obtained up to each day.

• Initialize Base Cases: Initialize the base cases, which are the solutions to the simplest subproblems. For this problem, the base case involves the first day where the maximum profit is zero.

• Fill the Table Bottom-Up: Iterate through the table, filling in entries based on the recurrence relation and previously computed values. Each entry in the table represents the solution to a subproblem.

• Return the Result: Once the table is filled, the solution to the original problem is found in the last entry of the table, representing the maximum profit that can be obtained by the end of the given days.

This approach has a time complexity of O(n) and an auxiliary space complexity of O(n).

Greedy Approach

The idea behind the Greedy approach is to minimize the cost price and maximize the selling price. We start by keeping track of the minimum buy price encountered so far. If the stock’s current price is lower than the previous buy price, we update the buy price. On the other hand, if the current price is greater than the buy price, we can sell the stock at this price to maximize profit. 

By iterating over the entire array, we can determine the maximum profit. The greedy approach to solving the “Best Time to Buy and Sell Stocks” problem involves iterating through the array of stock prices once and making a series of locally optimal choices to maximize the overall profit.

The key insight is to buy the stock at a local minimum (low price) and sell it at a local maximum (high price). Let’s understand with an example:

Let’s suppose we have, Prices array = [8,1,2,4,7,3]

In this example, we have to iteratively identify days where buying and selling can result in a positive profit. Specifically, we look for days where the stock price is lower (a potential buying opportunity) and the subsequent days where the stock price is higher (a potential selling opportunity).

Let’s see the iteration step by step:

Initialize the cur_day = prices[0] i.e. 8, and start iterating from index = 1.

Index: 1 Since prices[1] – cur_day i.e. 1 – 8 = -7 which is less than 0, so update the buying price as cur_day = 1 

Index: 2 Now price[2]>cur_buy so we, prices[2] – cur_day i.e. 2 – 1 = 1 is greater than 0, update the max_profit as 1. And keep cur_day the same on price[1]. 

Index: 3 Now price[3]>cur_day so we, prices[3] – cur_day i.e. 4 – 1 = 3 is greater than max_profit, update the max_profit as 3. And keep cur_day the same on price[1]. 

Index: 4 Now price[4]>cur_day so we, prices[4] – cur_day i.e. 7 – 1 = 6 is greater than max_profit, update the max_profit as 6. And keep cur_day the same on price[1].

Index: 5 Now, as prices[5] is greater than curr_day, prices[5] – curr_day, i.e., 3 – 1 = 2, is not greater than max_profit. So, max_profit will remain the same. This will be our maximum profit as we have iterated through all elements.

C++ Code

Below is the C++ program to solve the ‘Best Time to Buy and Sell Stock’ programming problem using greedy approach:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int cur_day = prices[0];
        int max_profit = 0;

        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] - cur_day < 0) {
                // If the current price is lower than the buying price,
                // update the buying price.
                cur_day = prices[i];
            } 
         	else {
                // Calculate and update the maximum profit if selling on the current day is profitable.
                max_profit = max(max_profit, prices[i] - cur_day);
            }
        }

        return max_profit;
    }
};

int main() {
    // Example prices array: [8, 1, 2, 4, 7, 3]
    vector<int> prices = {8, 1, 2, 4, 7, 3};

    // Create an instance of the Solution class
    Solution solution;

    // Calculate and print the maximum profit
    int result = solution.maxProfit(prices);
    cout << "Maximum Profit: " << result << endl;

    return 0;
}

Java Code

Check the Java program for the greedy approach below:

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int curDay = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - curDay < 0) {
                // If the current price is lower than the buying price,
                // update the buying price.
                curDay = prices[i];
            } else {
                // Calculate and update the maximum profit if selling on the current day is profitable.
                maxProfit = Math.max(maxProfit, prices[i] - curDay);
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        // Example prices array: [8, 1, 2, 4, 7, 3]
        int[] prices = {8, 1, 2, 4, 7, 3};

        // Create an instance of the Solution class
        Solution solution = new Solution();

        // Calculate and print the maximum profit
        int result = solution.maxProfit(prices);
        System.out.println("Maximum Profit: " + result);
    }
}

Python Code

We also provided the Python program to solve this leetcode problem:

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        cur_day = prices[0]
        max_profit = 0

        for i in range(1, len(prices)):
            if prices[i] - cur_day < 0:
                # If the current price is lower than the buying price,
                # update the buying price.
                cur_day = prices[i]
            else:
                # Calculate and update the maximum profit if selling on the current day is profitable.
                max_profit = max(max_profit, prices[i] - cur_day)

        return max_profit

# Example prices array: [8, 1, 2, 4, 7, 3]
prices = [8, 1, 2, 4, 7, 3]

# Create an instance of the Solution class
solution = Solution()

# Calculate and print the maximum profit
result = solution.maxProfit(prices)
print("Maximum Profit:", result)

Output:

Maximum Profit: 6

The time complexity of the code is O(n), where n is the length of the prices array. The algorithm iterates through the array once, performing constant-time operations for each element.

The space complexity of the code is O(1), which means it uses constant space regardless of the input size. The algorithm only uses a constant number of variables (cur_day and max_profit) to keep track of the current buying day and the maximum profit.

Comparison of all Approaches

Let’s see a quick review of recursive, dynamic programming, and greedy methods:

Conclusion

In this article, we explored the three different approaches to solve the leet code problem of ‘Best Time to Buy and Sell Stock’. The greedy approach being the most efficient approach involves iteratively identifying buying and selling opportunities to maximize profit. This approach is straightforward and intuitive and can be solved with the time complexity of O(n).