Best time to buy and sell stock

Intuition:

As we need to find the maximum profit, the idea is to buy the stock at its lowest price and sell it at its highest price. We can attempt to sell the stock every day and determine the maximum profit achievable by selling it on that specific day. Ultimately, we return the maximum of these individual maximum profits as our answer.

To compute the maximum profit on a particular day, given the selling price, we need to identify the buying price. To maximize the profit on day, the buying price should be the lowest stock price observed from day 0 to the present day(as shown in the graph). This approach enables us to accurately track the optimal buying price for any given day.

Approach:

Initialize a variable ‘maxProfit’ to 0 and declare another variable ‘mini’ which we will use to keep track of the buying price (minimum price from day 0 to current day) for selling the stock.

Traverse the array from index 1 to n-1. We started at index 1 because buying and selling the stock on the 0th day will give us a profit of 0, which we have initialized our maxProfit as already.

In each iteration, try to find the curProfit. The selling price will be the current element and ‘mini’ will give us the buying price. Calculate the curProfit. If it is more than the existing profit value (maxProfit), we update the maxProfit value.

Before going to the next iteration, check if the current price (Arr[i]) is less than the mini value, and assign it as the new 'mini' value. In this way, we keep track of the buying price in a single iteration itself.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find maximum profit
    int stockBuySell(vector<int> &arr, int n) {
        int maxProfit = 0;
        // Initialize mini to the first element of arr
        int mini = arr[0]; 

        // Traverse through the array 
        for (int i = 1; i < n; i++) {
            // Calculate current profit
            int curProfit = arr[i] - mini; 
            
            // Update maxProfit if curProfit is larger
            maxProfit = max(maxProfit, curProfit); 
            
            // Update mini to minimum value encountered so far
            mini = min(mini, arr[i]); 
        }
        // Return the maximum profit
        return maxProfit; 
    }
};

int main() {
    vector<int> Arr = {7, 1, 5, 3, 6, 4};
    int n = 6;

    // Create an instance of Solution class
    Solution sol;

    // Call maximumProfit function and print the result
    cout << "The maximum profit by selling the stock is " << sol.stockBuySell(Arr,6) << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to calculate the maximum profit earned
    public int stockBuySell(int[] arr, int n) {
        int maxProfit = 0;
        // Initialize mini to the first element of arr
        int mini = arr[0]; 

        // Traverse through the array 
        for (int i = 1; i < n; i++) {
            // Calculate current profit
            int curProfit = arr[i] - mini; 
            
            // Update maxProfit if curProfit is larger
            maxProfit = Math.max(maxProfit, curProfit); 
            
            // Update mini to minimum value encountered so far
            mini = Math.min(mini, arr[i]); 
        }
        // Return the maximum profit
        return maxProfit; 
    }

    public static void main(String[] args) {
        int[] Arr = {7, 1, 5, 3, 6, 4};
        int n = 6;

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

        // Call stockBuySell function and print the result
        System.out.println("The maximum profit by selling the stock is " + sol.stockBuySell(Arr, n));
    }
}
class Solution:
    # Function to calculate the maximum profit earned
    def stockBuySell(self, arr, n):
        maxProfit = 0
        # Initialize mini to the first element of arr
        mini = arr[0]

        # Traverse through the array
        for i in range(1, n):
            # Calculate current profit
            curProfit = arr[i] - mini
            
            # Update maxProfit if curProfit is larger
            maxProfit = max(maxProfit, curProfit)
            
            # Update mini to minimum value encountered so far
            mini = min(mini, arr[i])

        # Return the maximum profit
        return maxProfit

if __name__ == "__main__":
    Arr = [7, 1, 5, 3, 6, 4]
    n = 6

    # Create an instance of Solution class
    sol = Solution()

    # Call stockBuySell function and print the result
    print("The maximum profit by selling the stock is", sol.stockBuySell(Arr, n))
class Solution {
    // Function to calculate the maximum profit earned
    stockBuySell(arr, n) {
        let maxProfit = 0;
        // Initialize mini to the first element of arr
        let mini = arr[0];

        // Traverse through the array
        for (let i = 1; i < n; i++) {
            // Calculate current profit
            let curProfit = arr[i] - mini;
            
            // Update maxProfit if curProfit is larger
            maxProfit = Math.max(maxProfit, curProfit);
            
            // Update mini to minimum value encountered so far
            mini = Math.min(mini, arr[i]);
        }
        // Return the maximum profit
        return maxProfit;
    }
}

function main() {
    const Arr = [7, 1, 5, 3, 6, 4];
    const n = 6;

    // Create an instance of Solution class
    const sol = new Solution();

    // Call stockBuySell function and print the result
    console.log("The maximum profit by selling the stock is", sol.stockBuySell(Arr, n));
}

main();

Complexity Analysis:

Time Complexity:O(N), As the whole array is being traversed only once.

Space Complexity:O(1), As no extra space is being used.

Problem List

Best time to buy and sell stock

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code