LeetCode: Best Time to Buy and Sell Stock

In this article, we will tackle the Best Time to Buy and Sell Stock problem from LeetCode. This problem is a classic algorithmic question that involves finding the best times to buy and sell a stock to maximize profit.

Problem Statement

The problem can be summarized as follows:

You have 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.

Write a function maxProfit that takes the array of prices as input and returns the maximum profit that can be achieved.

Approach and Code

We can solve this problem efficiently using a simple approach. We will iterate through the array of prices and keep track of the minimum price we've seen so far. For each day, we calculate the potential profit by subtracting the minimum price from the current price. We update the maximum profit if the potential profit is greater than the current maximum profit.

Here's the TypeScript code for this approach:

function maxProfit(prices: number[]): number {
  let minPrice = Infinity
  let maxProfit = 0

  for (let price of prices) {
    if (price < minPrice) {
      minPrice = price
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice
    }
  }

  return maxProfit
}

Example

Let's take an example to understand how the function works. Consider the following prices array:

const prices = [7, 1, 5, 3, 6, 4]
const result = maxProfit(prices)
console.log(result) // Output: 5 (Buy at 1 and sell at 6)

Conclusion

The "Best Time to Buy and Sell Stock" problem can be efficiently solved by keeping track of the minimum price and calculating potential profits. The provided TypeScript solution demonstrates how to implement this approach.

For further practice and exploration, you can visit the LeetCode problem page and try out different test cases.

Resources

Here are some top resources to learn more about algorithms, data structures, and problem-solving techniques:

1. Cracking the Coding Interview: 189 Programming Questions and Solutions
2. System Design Interview – An insider's guide Volume 1
3. System Design Interview – An insider's guide Volume 2
4. Daily Coding Problem
5. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
6. LeetCode - The official LeetCode platform for practicing coding problems.
7. GeeksforGeeks - A website with a wide range of computer science topics and coding challenges.
8. Cracking the Coding Interview by Gayle Laakmann McDowell - A comprehensive book on coding interviews and algorithms.

Remember, consistent practice and learning from various sources will improve your problem-solving skills and algorithmic thinking.

Happy coding!