Visualization
The visualization below demonstrates how the algorithm works. The green bar represents the current buy position (left pointer), and the red bar represents the current sell position (right pointer).
Status: Ready
Best Time to Buy and Sell Stock Algorithm
This algorithm solves the problem of finding the best time to buy and sell stock to maximize profit. It uses a two-pointer approach where:
- The "left" pointer represents the current buy day.
- The "right" pointer represents the current sell day.
- At each step, we check if selling on the "right" day yields a profit greater than any previously observed profit. If it does, we update the maximum profit.
- If not, we move the "left" pointer to the current "right" pointer to try a new potential buy day.
- The algorithm proceeds until the "right" pointer has visited all days. The maximum profit observed during this process is the final result.
Step-by-Step Process:
Let’s break down the algorithm into clear steps:
- Initially, both the "left" pointer (buy day) and the "right" pointer (sell day) are set to the first and second elements in the prices array.
- The "left" pointer is updated only when the price on the "left" is greater than the price on the "right". Otherwise, we calculate the profit and compare it with the current maximum gain.
- The "right" pointer moves towards the end of the array to check subsequent days for a potential sell.
- By the time the "right" pointer has traversed the entire array, the algorithm has evaluated every possible buy-sell pair and returns the maximum profit.
Why This Works:
The algorithm ensures the buy is done on the left-most (earliest) possible day and the sell is done on the right-most (latest) possible day. This maximizes profit by buying low and selling high.
Because we are only traversing the array once, the time complexity is O(n), making this approach very efficient.