Topic: Learning notes

LeetCode 121: Best Time to Buy and Sell Stock in TypeScript

Replace nested transaction checks with one scan that tracks the lowest purchase price, including the correctness argument for a two-pointer solution and its O(n) cost.

The first natural solution checks every buy day against every later sell day. It is easy to write and correct, but it does too much work on a large input. Keeping the lowest purchase price seen so far reduces the two loops to one scan.

Problem

Original problem: LeetCode 121: Best Time to Buy and Sell Stock

Given prices, where prices[i] is the price on day i, make at most one purchase and one later sale. Return the largest profit. Return 0 if no positive profit is possible.

Brute force checks every transaction

function maxProfitBruteForce(prices: number[]): number {
  let bestProfit = 0;

  for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
    for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
      bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay]);
    }
  }

  return bestProfit;
}

This code enumerates every valid buy and sell pair, then keeps the largest difference. It is correct. The problem is that every buy day scans the later sell days again. There are n(n - 1) / 2 possible pairs in the worst case, so the time cost is O(n²) and auxiliary space is O(1).

The input may contain 10^5 prices. A nested loop would make roughly five billion comparisons, which is far too much work.

Two pointers

function maxProfit(prices: number[]): number {
  let p1 = 0;
  let p2 = 1;
  let bestProfit = 0;

  while (p2 < prices.length) {
    if (prices[p1] > prices[p2]) {
      p1 = p2;
    } else {
      bestProfit = Math.max(bestProfit, prices[p2] - prices[p1]);
    }

    p2 += 1;
  }

  return bestProfit;
}

This approach is correct. p1 keeps the best purchase day so far and p2 considers each later day as a possible sale. When prices[p2] is lower, the previous purchase day can be discarded. For every future sale day, buying at the lower price produces the same or greater profit.

It does not skip days in the middle. p2 still visits every day. It discards a higher old purchase price. That distinction explains why the running time is O(n).

The first version reset p2 to p1 + 1 after a new low. Incrementing p2 once at the end of every iteration has the same effect and keeps the loop condition shorter.

An equivalent version that is easier to explain

This is not asymptotically faster. Both solutions take O(n) time and O(1) auxiliary space. The difference is only how clearly the state is named.

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

  for (let day = 1; day < prices.length; day += 1) {
    bestProfit = Math.max(bestProfit, prices[day] - minPrice);
    minPrice = Math.min(minPrice, prices[day]);
  }

  return bestProfit;
}

minPrice names exactly what it holds. On day day, first calculate the best profit from selling today after buying on an earlier day. Then include today’s price when updating the minimum. There is no pointer reset to describe, which usually makes this version easier to present in an interview.

Why one scan is correct

Before processing day day, minPrice is the smallest value in prices[0] through prices[day - 1]. bestProfit is the largest legal profit whose sale day is before day.

If the sale happens today, the best possible purchase price is the lowest earlier price. Therefore prices[day] - minPrice covers the best transaction that sells today. After updating bestProfit, including today’s price in minPrice establishes the same conditions for the next iteration.

Day 0 has no earlier buy day, so the loop starts at index 1. The problem guarantees at least one value. If prices only fall or remain equal, no difference raises bestProfit above its initial value of 0.

Minimal verification

import assert from "node:assert/strict";

assert.equal(maxProfit([1, 1, 1]), 0);
assert.equal(maxProfit([7, 6, 5, 4, 3]), 0);
assert.equal(maxProfit([12, 9534, 433, 121, 3463, 461, 22, 534, 1, 1457, 2, 3321]), 9522);
assert.equal(maxProfit([2]), 0);

node:assert/strict throws when a comparison fails, so it is more useful than checking console.log() output by eye. The Node.js assert documentation describes strict assertions.

Complexity and transferable idea

The brute-force version takes O(n²) time. The optimized version takes O(n). Both keep a fixed number of numeric variables, so their auxiliary space is O(1).

The important idea is to compress all earlier purchase candidates into one minimum. Once a new lower price appears, older higher prices cannot improve any future sale. Similar discard rules appear in interval optimization and monotonic data-structure problems.

Common mistakes

• Allowing the purchase and sale on the same day when the problem requires the purchase first.
• Keeping a higher purchase price after a new lower price appears.
• Calling a nested loop O(n), or calling a fixed number of variables O(n) space.
• Testing only rising prices and missing falling, equal, and one-element arrays.

References

• LeetCode 121: Best Time to Buy and Sell Stock: original problem, examples, and constraints.
• TypeScript Handbook: More on Functions: function parameter and return-type syntax.
• Node.js: assert.strictEqual(): strict equality assertions.