I recently tackled a classic LeetCode problem: "Best Time to Buy and Sell Stock." This problem asks you to find the maximum profit you can make by buying and selling a stock once. Let's dive into the different approaches I explored, along with their complexities. Here's the URL of the problem: <h2>Brute Force Approach (Time Complexity: O(n^2))</h2>The most straightforward solution might be to compare every element in the array with all the remaining elements. For each price, we calculate the profit it would generate if sold on a later day. We then keep track of the maximum profit encountered. This approach, however, suffers from high time complexity and resulted in Time Limit Exceeded. <h2>Two Pointer Approach (Time Complexity: O(n))</h2>To improve efficiency, we can leverage the fact that we're buying before selling. We can introduce two pointers:<ul><li>buy: Points to the current potential buying price.</li><li>sell: Points to the selling price candidate.</li></ul>The idea is to iterate through the prices array, starting from the third element (since the first two elements are used for buying and selling). We continuously check if the difference between the sell price (current element) and the buy price is greater than the current maximum profit. If true, we update the maximum profit. Otherwise, we update the buy pointer to the current element (potentially a lower buying price) and move the sell pointer one step forward.This approach offers a significant improvement in time complexity, reaching O(n) as we only iterate through the array once. <h2>Greedy Approach (Time Complexity: O(n)) </h2>We can achieve a similar time complexity with a greedy approach. The key here is to understand that the maximum profit can only be achieved if we buy low and sell high. Therefore, we can iterate through the price array and keep track of the minimum price encountered so far. This represents the potential buying price. You can learn more about the code samples here: https://dev.to/this-is-learning/leetcode-problem-121-best-time-to-buy-and-sell-stock-5d2b And learn more about me here: https://next-js-portfolio-two-ebon.vercel.app/en

LeetCode Problem 121: Best Time to Buy and Sell Stock

Useful links

Company

Information

Content Writers

Freelancers

Freelance Jobs

Online Jobs

Designers

Developers

Translations