Best Time to Buy and Sell Stock leetcode solution

The "Best Time to Buy and Sell Stock" problem on LeetCode can be solved using a simple approach based on finding the minimum price and the maximum profit.

The problem statement asks us to find the maximum profit that can be obtained by buying and selling a stock on consecutive days. The input is an array of prices, where each element represents the price of the stock on a particular day.

To solve this problem, we can iterate through the array of prices and keep track of the minimum price we have seen so far and the maximum profit we can obtain. We start with an initial minimum price of the first element and an initial maximum profit of 0.

Here is the step-by-step explanation of the solution:

  1. Initialize two variables: minPrice and maxProfit to keep track of the minimum price and maximum profit, respectively.
  2. Iterate through the array of prices from the second element (index 1) to the end.
  3. At each iteration, check if the current price is less than the minimum price. If it is, update the minimum price to the current price.
  4. Otherwise, calculate the profit by subtracting the minimum price from the current price. If the calculated profit is greater than the maximum profit, update the maximum profit.
  5. After the iteration, return the maximum profit.

The time complexity of this solution is O(n), where n is the length of the input array, since weBest Time to Buy and Sell Stock Leetcode Solution in C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int i = 0; i < prices.size(); i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
};

Explanation:

  1. Declare variables minPrice and maxProfit and initialize minPrice to INT_MAX and maxProfit to 0.
  2. Iterate through the prices array using a for loop.
  3. If the current price is less than minPrice, update minPrice to the current price.
  4. If the difference between the current price and minPrice is greater than maxProfit, update maxProfit to this difference.
  5. Return the final maxProfit value.