Hello, Welcome to my Day 7 of #30Days of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode's question 121 - Best Time to Buy and Sell Stock .

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> 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.

Example 1:

  Input: prices = [7,1,5,3,6,4]
  Output: 5
  Explanation: 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.

Example 2:

  Input: prices = [7,6,4,3,1]
  Output: 0
  Explanation: In this case, no transactions are done and the max profit = 0.

Thought Process/ Intuition

My first thoughts on how to solve this problem would be to iterate through the array of stock prices and keep track of the minimum price seen so far and the maximum profit that can be made by selling the stock at the current price.

At each day, I would calculate the difference between the current price and the minimum price seen so far. If this difference is greater than the maximum profit, I would update the maximum profit.

After iterating through the entire array, I would return the maximum profit. This is a straightforward approach that has a time complexity of O(n), where n is the length of the input array.

The Approach

As mentioned in my first thoughts, my approach to solving the problem is to iterate through the array of stock prices and keep track of the minimum price seen so far and the maximum profit that can be made by selling the stock at the current price.

Here are the steps to my approach:

Initialize the minimum price to be the first price in the array and the maximum profit to be 0.

Iterate through the array of stock prices starting from the second day.

For each day, calculate the difference between the current price and the minimum price seen so far.

If this difference is greater than the maximum profit, update the maximum profit to this new value.

If the current price is less than the minimum price seen so far, update the minimum price to be the current price.

After iterating through the entire array, return the maximum profit.

This approach has a time complexity of O(n), where n is the length of the input array, since we are only iterating through the array once.

Code Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)< 2:
            return 0

        min_ptr = 0
        max_ptr = 1
        max_profit = 0

        while max_ptr < len(prices):
            if prices[max_ptr] <prices[min_ptr]:
                min_ptr = max_ptr
            else:
                profit = prices[max_ptr] - prices[min_ptr]
                if profit > max_profit:
                    max_profit = profit
            max_ptr += 1
        return max_profit

The above solution using the two pointer approach method. The two-pointer approach involves using two pointers, one for the minimum price and one for the maximum profit. We can initialize both pointers to point to the first element of the array. Then we move the minimum pointer forward until we find a lower price. If we find a lower price, we move the minimum pointer to that index, and then move the maximum pointer to the next index. We calculate the profit between the current minimum price and the current maximum price and update the maximum profit if the current profit is greater than the previous maximum profit.

Complexity

Time complexity:

0(n)

The time complexity of the above solution is O(n), where n is the length of the input array. This is because we are only iterating through the array once, and performing constant-time operations for each element.

Space complexity:

0(1)

The space complexity of the solution is O(1), because we are only using a constant amount of extra space to keep track of the minimum price seen so far and the maximum profit that can be made. We are not using any additional data structures that grow with the size of the input array.

Conclusion

In conclusion, the solution that we have discussed above is an efficient and optimal way to solve the problem of finding the maximum profit that can be made from buying and selling a stock. It uses a simple and intuitive approach of keeping track of the minimum price seen so far and the maximum profit that can be made, and iterates through the array of stock prices only once. This results in a time complexity of O(n) and a space complexity of O(1), making it a very efficient and optimal solution for the problem. The solution can handle very large input arrays and can solve the problem in a reasonable amount of time. Therefore, this solution can be used to solve similar problems where we need to find the maximum profit that can be made from buying and selling a commodity over a period of time.

Allan Kiche's Blog