Mark As Completed Discussion

Whenever you are struggling for an answer, try to identify some pattern in the examples to exploit. A realization that may help is the fact that because the selling price must come after the buy price, we can start our iteration from the end of the array. What are the things we need to keep track of?

The realization that we can start our iteration from the end of the array opens up an interesting perspective on the problem. Let's break it down into a step-by-step process:

Reversing the Perspective

Step Five

Why Iterate from the End?

  • Starting from the end allows us to look at the problem differently: instead of focusing on the buying price first, we can focus on the selling price.
  • This method still aligns with the problem constraint that selling must come after buying.

How This Approach Works

  • By iterating from the end, we're effectively looking at the future prices first and then determining the best buying price for those future selling prices.
  • We ensure that the selling price always comes after the buying price by updating our maxPrice only when we find a higher price as we move towards the beginning of the array.
  • It's still an O(n) solution, as we're only iterating through the array once.