DEV Community

Cover image for LeetCode Meditations: Best Time to Buy and Sell Stock
Eda
Eda

Posted on • Edited on • Originally published at rivea0.github.io

LeetCode Meditations: Best Time to Buy and Sell Stock

Make sure to read the Sliding Window post first!


The description for this problem states:

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.

For example:

maxProfit([7, 1, 5, 3, 6, 4]);
// -> 5
// Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
// Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.


maxProfit([7, 6, 4, 3, 1]);
// -> 0
// In this case, no transactions are done and the max profit = 0.
Enter fullscreen mode Exit fullscreen mode

This problem is a perfect example where we can use the sliding window technique. But one important thing to notice is that we need to sell the stock at a future date; that is, the right end of our window should be at least one step ahead of the left end.

We can initialize left and right pointers (remember the Two Pointers technique?); left at the first index, right at left + 1. If the price on the left is less than the one on the right, that means we can make a profit, so we can get their difference and update the maximum difference that we keep track of. Otherwise, we'll just update left to be where right is, because right will be the minimum value we have seen so far. Either way, we'll update the right pointer until it points to the last element.

It looks like this in TypeScript:

function maxProfit(prices: number[]): number {
  let left = 0;
  let right = left + 1;
  let maxDiff = 0;

  while (right < prices.length) {
    if (prices[left] < prices[right]) {
      let diff = prices[right] - prices[left];
      maxDiff = Math.max(maxDiff, diff);
    } else {
      left = right;
    }

    right++;
  }

  return maxDiff;
};
Enter fullscreen mode Exit fullscreen mode

This is an example of the dynamically sized sliding window technique, where we adjust our window size dynamically based on conditions, instead of keeping it fixed to some value. It's specifically a version of fast/catch-up because while the right pointer is always increasing, the left pointer jumps to catch up with the right pointer in the else block.

Time and space complexity

The time complexity for this solution is O(n)O(n) because we iterate once through the items of the array. And, the space complexity is O(1)O(1) as we don't use any additional space where the size depends on the size of the input array.


That's it for this problem, we can take a deep breath now. Next up is Longest Substring Without Repeating Characters — until then, happy coding.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay