Best Time to Buy and Sell Stock

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

You are given an array 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.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples:

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

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

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

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Input: prices = [3,2,6,5,0,3]

Output: 4

Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.

Constraints

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴

Editorial

Intuition:

The key insight is that the maximum profit is achieved by buying at the lowest price seen so far and selling at a higher price later. By tracking the minimum price encountered during the iteration, we can compute the profit for each day as the current price minus this minimum and keep the maximum profit.

Approach:

Initialize min_price to a large value (e.g., INT_MAX or Infinity) and max_profit to 0.
Iterate through each price in the prices array.
For each price, update min_price if the current price is lower than the current min_price.
Calculate the potential profit as current price - min_price and update max_profit if this profit is greater.
After processing all prices, return max_profit.

class Solution {
public:
    int maxProfit(vector& prices) {
        int min_price = INT_MAX;
        int max_profit = 0;
        for (int price : prices) {
            if (price < min_price) {
                min_price = price;
            }
            int profit = price - min_price;
            if (profit > max_profit) {
                max_profit = profit;
            }
        }
        return max_profit;
    }
};
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            }
            int profit = price - minPrice;
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
        return maxProfit;
    }
}
class Solution:
    def max_profit(self, prices):
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price
            profit = price - min_price
            if profit > max_profit:
                max_profit = profit
        return max_profit
class Solution {
    maxProfit(prices) {
        let minPrice = Infinity;
        let maxProfit = 0;
        for (let price of prices) {
            if (price < minPrice) {
                minPrice = price;
            }
            let profit = price - minPrice;
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
        return maxProfit;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of the prices array, since we traverse the array once.

Space Complexity: O(1), as we use only a constant amount of extra space for variables.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories