Best Time to Buy and Sell Stock

  1. Clarify the problem:

    • The problem requires finding the maximum profit that can be achieved by buying and selling a stock.
    • We can only make one transaction (buy and sell) of the stock.
    • We need to return the maximum profit.

  2. Analyze the problem:

    • Input: An array of prices representing the stock prices on different days.
    • Output: An integer representing the maximum profit.
    • Constraints:
      • The input array can have 0 or more elements.
      • The prices are given for consecutive days, and the order represents the chronological order.
      • We can only make one transaction (buy and sell) of the stock.

  3. Design an algorithm:

    • To solve the problem using the two-pointer technique:
      • Initialize two pointers, buy and sell, both pointing to the first element of the array.
      • Iterate through the array using the sell pointer.
      • Compare the price at the sell pointer with the price at the buy pointer.
      • If the price at the sell pointer is less than the price at the buy pointer, update both pointers to the current position.
      • If the price at the sell pointer is greater than the price at the buy pointer, calculate the potential profit (price[sell] - price[buy]).
      • If the potential profit is greater than the current maximum profit, update the maximum profit.
      • Continue the iteration until the sell pointer reaches the end of the array.
      • Return the maximum profit.

  4. Explain your approach:

    • To solve the problem using the two-pointer technique, we initialize two pointers, buy and sell, both pointing to the first element of the array.
    • We iterate through the array using the sell pointer.
    • For each element, we compare the price at the sell pointer with the price at the buy pointer.
    • If the price at the sell pointer is less than the price at the buy pointer, it means we have found a potential buying opportunity. We update both pointers to the current position.
    • If the price at the sell pointer is greater than the price at the buy pointer, it means we have found a potential selling opportunity. We calculate the potential profit by subtracting the price at the buy pointer from the price at the sell pointer.
    • If the potential profit is greater than the current maximum profit, we update the maximum profit.
    • We continue the iteration until the sell pointer reaches the end of the array.
    • Finally, we return the maximum profit.

  5. Write clean and readable code:

python
def maxProfit(prices):
    if not prices:
        return 0

    buy = 0
    sell = 0
    max_profit = 0

    for sell in range(1, len(prices)):
        if prices[sell] < prices[buy]:
            buy = sell
        else:
            max_profit = max(max_profit, prices[sell] - prices[buy])

    return max_profit
  1. Test your code:
    • Test cases:
      • Test Case 1:
        • Input: [7,1,5,3,6,4]
        • Explanation: The prices on different days are [7, 1, 5, 3, 6, 4].
        • The maximum profit can be achieved by buying on day 2 (price = 1) and selling on day 5 (price = 6), resulting in a profit of 6 - 1 = 5.
        • Expected output: 5
      • Test Case 2:
        • Input: [7,6,4,3,1]
        • Explanation: The prices on different days are [7, 6, 4, 3, 1].
        • Since the prices are decreasing every day, there is no opportunity to make a profit. Thus, the maximum profit is 0.
        • Expected output: 0
python
# Test case 1
prices = [7,1,5,3,6,4]
print(maxProfit(prices))  # Output: 5

# Test case 2
prices = [7,6,4,3,1]
print(maxProfit(prices))  # Output: 0

  1. Optimize if necessary:

    • The solution using the two-pointer technique is already optimized with a time complexity of O(n), where n is the number of elements in the input array.
    • There is no need for further optimization.

  2. Handle error cases:

    • If the input array is empty, the algorithm returns 0, as there are no prices available to make a profit.

  3. Discuss complexity analysis:

    • The time complexity of the algorithm is O(n), where n is the number of elements in the input array.
    • The algorithm performs a single pass through the array to find the maximum profit by updating the buy and sell pointers.
    • The space complexity is O(1) since the algorithm uses only a constant amount of space to store the pointers and the maximum profit variable.
Next Post Previous Post