Each number is a stock's price on one day. Buy on one day and sell on a later day. Return the maximum profit, or 0 if no profit is possible.
DSA Animator › DSA Revision › Arrays › Best Time to Buy and Sell Stock
Remember: keep the cheapest price so far, and ask what selling today would earn. The order of days matters, so one left to right pass handles it. The video solves Best Time to Buy and Sell Stock (LeetCode 121, Easy) with the One Pass pattern from the Arrays topic, and you can replay every step in the interactive Best Time to Buy and Sell Stock animation.
Each number is a stock's price on one day. Buy on one day and sell on a later day. Return the maximum profit, or 0 if no profit is possible.
For 7, 1, 5, 3, 6, 4, buy at 1 and sell at 6. The profit is 5.
Buying at the lowest price overall does not always work, because the selling day must come after it. And checking every pair of days is O of n squared.
Walk through the days once, and remember the cheapest price so far. On each day, imagine selling today: the profit is today minus the cheapest so far. Keep the best profit seen.
Day 0: the cheapest is 7, and the profit is 0. Day 1: 1 is cheaper, so the cheapest becomes 1. Day 2: selling at 5 gives a profit of 4. Day 3: selling at 3 gives only 2. Day 4: selling at 6 gives 5, the new best. Day 5: selling at 4 gives 3, so the best stays 5.
In code, track the minimum price and the best profit. For each price, update the minimum, then update the best with price minus minimum. One pass, so it's O of n time and O of 1 space.
Remember: keep the cheapest price so far, and ask what selling today would earn. The order of days matters, so one left to right pass handles it.