121. Best time to buy and sell stocks - 1 | Leetcode
The "Best time to buy and sell stocks" problem on LeetCode is a classic algorithmic problem where the task is to identify the optimal day for buying and selling a stock to maximize profit. Although one may consider finding the minimum and maximum values in the array to determine the maximum profit, there is a catch. For example, in the case of prices = [7,6,4,3,1], it is not possible to buy the stock on day 6 and sell it on day 1. Thus, an alternative strategy is required to determine the best feasible buying and selling days while considering the chronological order.
Explanation:
To solve the problem, we employ a two-pointer approach: the Left pointer indicates the position for buying the stock, while the Right pointer indicates the position for selling the stock.
Initially, we set the Left and Right pointers to the first and second positions of the array, respectively. We also initialize the variable max_profit to zero.
Next, we enter a while loop that continues until the Right pointer is less than the length of the array. For each iteration, we examine the prices at the Left and Right pointers.
In the first step, we observe price[left] = 7 and price[right] = 1, resulting in a profit of -6. As price[left] is greater than price[right], we increment the Left pointer and advance the Right pointer by one position. This ensures that the Left pointer always corresponds to the minimum value.
Moving to the second step, we find price[left] = 1 and price[right] = 5, resulting in a profit of 4. As price[left] is less than price[right], indicating a potential profit, we update max_profit accordingly and solely increment the Right pointer.
Proceeding to the third step, we encounter price[left] = 1 and price[right] = 3, yielding a profit of 2. Similar to the previous step, we compare the current profit (2) with the previous max_profit (4), select the maximum value, update max_profit, and increment the Right pointer.
In the fourth step, with price[left] = 1 and price[right] = 6, the profit is 5. Following the same logic as before, we compare the current profit (5) with the previous max_profit (4), update max_profit if necessary, and advance the Right pointer.
Finally, in the fifth step, price[left] = 1 and price[right] = 4, resulting in a profit of 3. We apply the same logic as in the previous steps.
Regarding the complexity analysis, let n represent the length of the array.
The time complexity of the algorithm is O(n) due to the while loop iterating through the array.
The space complexity is O(1) since we utilize a constant amount of additional space.
0:00 - Introduction and reading of the problem
0:45 - Explanation
07:44 - Coding the solution
#leetcode #datastructures #interviewquestions