Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction(i.e., buy one and sell one share of the stock), design an algorithm
to find the maximum profit.
Examples:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 =5 (not 7-1 = 6, as the selling price needs to be larger than the buying price)
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e., max profit = 0
Solution: Recursive
class Solution:
def recursive(self, i: int, prices):
if i == 0: return 0
max_val = self.recursive(i-1, prices)
for j in range(1, i):
max_val =max(max_val, prices[i-1]-prices[j-1])
return max_val
Time Complexity
The time complexity of the recursive solution is exponential. This is because, for each day, the function explores all possible transactions with previous days j to find the maximum profit. The number of recursive calls grows exponentially with the input size i. Therefore, the time complexity is O(2^n), where n is the number of days.
Space Complexity
The space complexity is O(n) due to the recursion depth. In each recursive call, the function explores the possibilities for the remaining days, and the maximum recursion depth is n. This results in a linear amount of space being used on the call stack.
Solution: Bottom-Up Dynamic Programming
class Solution:
def buy_sell_bottom_up(self, n, prices):
R ={}
R[0] = 0
for i in range(1, n):
R[i] = R[i-1]
for j in range(i):
R[i] =max(R[i], prices[i]-prices[j])
return R[n-1]
Time Complexity
The time complexity of this bottom-up solution is O(n^2). The outer loop runs for n-1 iterations, and for each iteration, the inner loop runs i times. As a result, the total number of operations is proportional to the sum of the first n-1 integers, which is on the order of O(n^2).
Space Complexity
The space complexity is O(n). The solution uses a dictionary R to store the maximum profit each day. The dictionary has most n entries where n is the number of days. Therefore, the space complexity is linear with respect to the input size.
Here's a similar solution with a space complexity of O(1).
class Solution:
def updated_buy_sell(self, nums):
max_profit = -float("inf")
min_val =nums[0]
for i in range(len(nums)):
for j in range(i, -1, -1):
if nums[j] < min_val:
min_val =nums[j]
max_profit =max(max_profit, nums[i] -min_val)
return max_profit
Solution: Optimized Bottom-Up Dynamic Programming
Here's an optimized version of the bottom-up solution above.
class Solution:
def buy_sell_bottom_up_optimized(self, n, prices):
R ={}
R[0] = 0
min_val=float("inf")
for i in range(1, n):
R[i] = R[i-1]
if prices[i] < min_val:
min_val = prices[i]
R[i] =max(R[i], prices[i]-min_val)
return R[n-1]
print(f"buy_sell bottom up optimized:: {sol.buy_sell_bottom_up_optimized(6, [7, 1, 5, 3, 6, 4])}")
print(f"buy_sell bottom up optimized:: {sol.buy_sell_bottom_up_optimized(5, [7, 6, 4, 3, 1])}")
An alternative optimized solution with a time complexity of O(n) and O(1) space complexity is here
class Solution:
def updated_buy_sell_opt(self, nums):
max_profit = -float("inf")
min_val =nums[0]
for i in range(len(nums)):
if nums[i] < min_val:
min_val =nums[i]
max_profit =max(max_profit, nums[i] -min_val)
return max_profit