Best Time to Buy and Sell Stock (opens in a new tab) Easy

Problem:

You are given an array of prices where prices[i] are the price of a given stock on the ith 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.

Example:

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.

Solution:

One way to solve this problem is to keep track of the minimum price seen so far and the maximum profit that can be obtained by selling on the current day. We can update these values as we iterate through the array.

In TypeScript:

function maxProfit(prices: number[]): number {
	let minPrice = Number.MAX_SAFE_INTEGER;
	let maxProfit = 0;
 
	for (let i = 0; i < prices.length; i++) {
		minPrice = Math.min(minPrice, prices[i]);
		maxProfit = Math.max(maxProfit, prices[i] - minPrice);
	}
 
	return maxProfit;
}

In Python3:

def maxProfit(prices: List[int]) -> int:
	minPrice = float('inf')
	maxProfit = 0
 
	for price in prices:
		minPrice = min(minPrice, price)
		maxProfit = max(maxProfit, price - minPrice)
 
	return maxProfit

The time complexity of this solution is O(n), where n is the length of the input array. The space complexity is O(1), because we only need to store two variables (minPrice and maxProfit) at any given time.