Best Time to Buy and Sell Stock - Leetcode 121 - TypeScript

Here's the Leetcode 121 solution using TypeScript.

Watch on Youtube

Leetcode 121 - Best Time to Buy and Sell Stock:

You are given an array prices where prices[i] is 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.

Approach

The goal is to find the maximum profit that you can obtain by buying and selling a stock given it's prices over time.

You can use a simple one-pass algorithm with two pointers, l and r, and track the buying and selling days.

Initialize l and r to the first and second days, respectively.

Then iterate through the array using a while loop.

In each iteration, check if the price on day l is less than the price on day r. If true, calculate the profit by subtracting the buying price (prices[l]) from the selling price (prices[r]) and update the maximum profit (max) only if the calculated profit is greater than the current maximum.

On the other hand, if the buying price is not less than the selling price, it means a better buying opportunity is found, so move the l pointer to the current selling day (r). This way you can ensure that the algorithm always looks for the lowest buying price before searching for a selling opportunity.

The final result is the maximum profit obtained by buying and selling the stock.

View on Excalidraw

Code Implementation

function maxProfit(prices: number[]): number {
  let l = 0
  let r = 1
  let max = 0

  while (r < prices.length) {
    if (prices[l] < prices[r]) {
      const profit = prices[r] - prices[l]
      max = Math.max(profit, max)
    } else l = r

    r++
  }

  return max
}

Time Complexity

The time complexity is O(n), where n is the length of the input array prices. The algorithm iterates through the array once, and each iteration involves constant-time operations.

Space Complexity

The space complexity is O(1) or constant. The algorithm uses only a constant amount of extra space for variables like l, r, max, and profit.

It doesn't require additional memory that grows with the size of the input array.