Best Time to Buy and Sell Stock -- Basic

Published: Jul 26, 2022

Easy Array DP

Problem Description

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.

Constraints:

  • 1 <= prices.length <= 10**5
  • 0 <= prices[i] <= 10**4

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Examples

example 1:
Input: prices = [7,1,5,3,6,4]
Answer: 5
Explanation: 5 is the best profit which is from buying on the index 1 an selling on the index 4.

example 2:
Input: prices = [7,6,4,3,1]
Answer: 0
Explanation: the array value is ever descreasing. There is no profit available.

How to Solve

The problems of the best time to buy and sell stock have variations. Each has a slight different criteria to find the answer. This is the most basic and easy buy-sell-stock problem.

We are allowed to buy and sell only once. The minimum price so far should be updated in each array index if necessary. If the price at the current index is not the minimum, calculate profit so far. Then, update the grand max profit comparing with the current profit.

Solution

#include <vector>
#include <iostream>
using namespace std;

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

class BestTimeToBuyAndSellStock {
    public int maxProfit(int[] prices) {
        int min_price = Integer.MAX_VALUE;
        int max_profit = 0;
        for (int i = 0; i < prices.length; ++i) {
            if (min_price > prices[i]) {
              min_price = prices[i];
            } else {
              max_profit = Math.max(max_profit, prices[i] - min_price);
            }
        }
        return max_profit;
    }
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min_price = Number.MAX_SAFE_INTEGER, max_profit = 0;
    for (let i = 0; i < prices.length; i++) {
      if (min_price > prices[i]) {
        min_price = prices[i];
      } else {
        max_profit = Math.max(max_profit, prices[i] - min_price)
      }
    }
    return max_profit;
};

from typing import List

class BestTimeToBuyAndSellStock:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, min_price = 0, float('inf')
        if not prices:
            return 0
        min_price = prices[0]
        for i in range(1, len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            else:
                max_profit = max(max_profit, prices[i] - min_price)
        return max_profit

# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
    min_price = 10**4 + 1
    max_profit = 0
    prices.each do |price|
      if min_price > price
        min_price = price
      else
        max_profit = [max_profit, price - min_price].max
      end
    end
    max_profit
end

Complexities

  • Time: O(n) – n: length of the input array.
  • Space: O(1)