Please see github.com/anusha-murali for all of my repositories.
Problem:
You are given an array prices
where prices[i]
is the price of a given stock on the $i$-th 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.
Solution 1: Naive Brute-Force Solution
def maxProfit(prices):
mProfit = 0
for i in range(len(prices)-1):
profit = max(prices[i+1:]) - prices[i]
if profit < 0:
profit = 0
mProfit = max(mProfit, profit)
return mProfit
Let us say that you are currently on the $i$-th day and are making a purchase on that day. So the price that you paid for the stock is prices[i]
. In order to maximize the profit, you will want to sell your stock on the future date when the stock price is the highest. The highest future price of the stock can be obtained by max(prices[i+1:])
. Hence the maximum profit for the purchase made on the $i$-th day is max(prices[i+1:]) - prices[i]
.
The maximum possible profit is the maximum of max(prices[i+1:]) - prices[i]
over all the days from i=0
to i=len(prices)-1
.
Runtime: Since the computation of max(prices[i+1:])
takes $n, n-1, \ldots, 1$ steps for each of $i = 0, 1, \ldots, n-1$, the total cost is $n(n+1)/2$. Hence the runtime is $O(n^2)$. Therefore, the above algorith will run into “Time Exceeded” error for very large $n$ on LeetCode.
Since we are only using two constant local variables, the space complexity is $O(1)$.
Solution 2: Two-Pointer Solution
def maxProfit(prices):
mProfit = 0
purchasePtr = salePtr = 0
for i in range(1, len(prices)):
if prices[i] > prices[purchasePtr]:
salePtr = i
else:
purchasePtr = i
if salePtr > purchasePtr:
mProfit = max(mProfit, prices[salePtr] - prices[purchasePtr])
return mProfit
In the two-pointer solution above, we maintain two pointers, namely, purchasePtr
and salePtr
, both of which are initialized to 0.
When the current price, prices[i]
is larger than the price currently indexed by the purchasePtr
, i.e: prices[purchasePtr]
, we would preferrably want to sell the set. So, we update the salePtr
to the current index. Otherwise, the current price is smaller or equal, so we update the purchasePtr
to i
.
If the price difference between the prices pointed to by the salePtr
and the purchasePtr
(i.e: prices[salePtr] - prices[purchasePtr]
), then we compare it with the current maximum profit, mProfit
and update it.
Once we reach the end of the prices
list, mProfit
will contain the maximum possible profit.
Runtime Since we are iterating through the for
loop only once, the runtime is $O(n)$. The space complexity is obviously $O(1)$.