Maximum Profit From Trading Stocks
MediumAsked by:
+1
More companies
24 views
Topics:
ArraysDynamic Programming
You are given two 0-indexed integer arrays prices and profits, representing the price and profit of each stock. You are also given an integer money, which represents your initial capital.
For every stock, you can buy at most one share. After buying any number of shares of stocks, you can sell them after one day and gain profits[i] - prices[i] for each share of the stock i that you bought.
Return the maximum profit you can have after buying and selling the stocks.
Note: There is no limit on the number of stocks you can buy.
Example 1:
Input: prices = [10,15,12,18,20], profits = [25,22,15,24,30], money = 100 Output: 105 Explanation: Buy stock 0, spend 10, and gain 25 - 10 = 15. Buy stock 2, spend 12, and gain 15 - 12 = 3. Buy stock 3, spend 18, and gain 24 - 18 = 6. The total profit is 15 + 3 + 6 = 24. After buying and selling these stocks, your money is 100 - 10 - 12 - 18 + 24 = 84. Buy stock 1, spend 15, and gain 22 - 15 = 7. Buy stock 4, spend 20, and gain 30 - 20 = 10. The total profit is 24 + 7 + 10 = 41. After buying and selling these stocks, your money is 84 - 15 - 20 + 41 = 90. The maximum profit you can have is 15 + 3 + 6 + 7 + 10 = 41. So your final money is 100 + 41 = 141.
Example 2:
Input: prices = [10,15,12,18,20], profits = [15,22,15,24,30], money = 100 Output: 177 Explanation: Buy stock 0, spend 10, and gain 15 - 10 = 5. Buy stock 1, spend 15, and gain 22 - 15 = 7. Buy stock 2, spend 12, and gain 15 - 12 = 3. Buy stock 3, spend 18, and gain 24 - 18 = 6. Buy stock 4, spend 20, and gain 30 - 20 = 10. The total profit is 5 + 7 + 3 + 6 + 10 = 31. After buying and selling these stocks, your money is 100 - 10 - 15 - 12 - 18 - 20 + 31 = 56. Buy stock 1, spend 15, and gain 22 - 15 = 7. Buy stock 3, spend 18, and gain 24 - 18 = 6. Buy stock 4, spend 20, and gain 30 - 20 = 10. The total profit is 31 + 7 + 6 + 10 = 54. After buying and selling these stocks, your money is 56 - 15 - 18 - 20 + 23 = 26. Buy stock 3, spend 18, and gain 24 - 18 = 6. The total profit is 54 + 6 = 60. After buying and selling these stocks, your money is 26 - 18 + 6 = 14. Buy stock 3, spend 14, and gain 24 - 18 = 6. The total profit is 60 + 6 = 66. So your final money is 100 + 66 = 166.
Constraints:
1 <= prices.length == profits.length <= 1051 <= prices[i], profits[i] <= 1050 <= money <= 109
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values for the stock prices in the `prices` array? Could prices be zero or negative?
- What should I return if the input array is empty or contains only one element? Should I return 0 in that case?
- Are there any restrictions on the number of transactions I can make on a single day? (e.g., can I buy and sell on the same day, or must I hold the stock overnight?)
- Is there a limit to the size of the `prices` array?
- Is it possible to have monotonically decreasing prices throughout the array? If so, what profit should I return?
Brute Force Solution
Approach
The brute force approach to maximizing stock trading profit involves considering every single possible buy and sell combination. We explore each pair of days to see if buying on one day and selling on another yields a profit. This ensures we find the absolute best, even if inefficiently.
Here's how the algorithm would work step-by-step:
- Start by picking the first day as the day to buy the stock.
- Then, try selling the stock on every single day that comes after the day you bought it.
- Calculate the profit for each of these buy-sell day pairs.
- Now, pick the second day as the day to buy the stock, and again, try selling on every day after that.
- Keep doing this for every single day as a potential buying day.
- As you check each possible combination, remember the highest profit you've found so far.
- After checking all the buy-sell day combinations, the highest profit you remembered is the answer.
Code Implementation
def max_profit_brute_force(stock_prices):
max_profit_so_far = 0
number_of_days = len(stock_prices)
for buy_day in range(number_of_days):
# Consider each day as a potential buying day
for sell_day in range(buy_day + 1, number_of_days):
# Try selling on every day after the buy day
profit = stock_prices[sell_day] - stock_prices[buy_day]
# Calculate profit for this buy-sell combination
max_profit_so_far = max(max_profit_so_far, profit)
# Update the maximum profit found so far
return max_profit_so_farBig(O) Analysis
Time Complexity
O(n²) – The outer loop iterates through each of the n days as a potential buying day. For each buying day, the inner loop iterates through the remaining days after the buying day to find a selling day. In the worst-case scenario, for the first buying day, we perform n-1 comparisons, for the second n-2, and so on, resulting in (n-1) + (n-2) + ... + 1 comparisons. This series approximates to n * (n-1) / 2, which simplifies to O(n²).
Space Complexity
O(1) – The brute force approach described only requires storing a variable for the current profit being calculated and a variable to store the maximum profit found so far. No additional data structures like arrays, lists, or hashmaps are created to store intermediate results or track visited elements. The amount of extra memory used does not depend on the input size N, where N represents the number of days in the stock price list. Therefore, the auxiliary space complexity is constant, O(1).
Optimal Solution
Approach
To maximize profit, we aim to buy low and sell high. Instead of checking all possible buy/sell combinations, we use a single pass to track the lowest buying price and sell whenever we see a higher price, accumulating profit along the way.
Here's how the algorithm would work step-by-step:
- Start by assuming you haven't bought any stock yet and set your potential buying price to the price of the stock on the first day.
- Look at the price on the next day. If it's higher than your potential buying price, calculate the profit you'd make by selling today and add it to your total profit. Also, reset your potential buying price to today's price, since you have now sold your stock.
- If the price is lower than your current potential buying price, update your potential buying price to the lower price, as you would rather buy at a cheaper price.
- Keep moving to the next day, repeating the previous two steps: either selling if the price is higher to make a profit, or updating your potential buying price if the price is lower.
- Continue this process until you've examined the stock price for every day.
- The total profit you've accumulated is the maximum profit you can make by buying and selling the stock.
Code Implementation
def max_profit_from_stocks(stock_prices):
max_profit = 0
potential_buying_price = stock_prices[0]
for current_price in stock_prices:
# If current price is higher, sell and add profit
if current_price > potential_buying_price:
max_profit += current_price - potential_buying_price
potential_buying_price = current_price
# Update the buying price if a lower price is found
elif current_price < potential_buying_price:
potential_buying_price = current_price
return max_profitBig(O) Analysis
Time Complexity
O(n) – The provided solution involves a single pass through the input array of stock prices. The algorithm iterates through each price once to determine the potential buying price and calculate profits. The number of operations is directly proportional to the number of days, which is the input size (n). Therefore, the time complexity is O(n).
Space Complexity
O(1) – The algorithm uses only a few constant space variables: one to store the potential buying price and another to accumulate the total profit. The number of variables does not depend on the input size (N), which represents the number of days for which stock prices are available. Therefore, the auxiliary space required remains constant regardless of the input size. This constant space usage simplifies to O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input array | Return 0 as no profit can be made without stock prices. |
| Input array with only one element | Return 0 as a single day cannot result in a buy and sell transaction. |
| Input array with monotonically decreasing prices (always going down) | Return 0 as there's no opportunity to buy low and sell high. |
| Input array with monotonically increasing prices (always going up) | Calculate profit by buying on day 0 and selling on the last day, or accumulate profit from each increasing day. |
| Input array with all identical values | Return 0 as there's no price difference to make a profit. |
| Integer overflow when accumulating profit with large price differences and many transactions | Use a data type that can accommodate larger values (e.g., long) for profit accumulation to avoid overflow. |
| Input array contains very large price values (close to maximum integer) | The algorithm should still work correctly as long as intermediate calculations don't overflow, address with larger data types if needed. |
| Alternating high and low prices creating many small profits | The greedy approach of buying low and selling high on each increasing day handles this efficiently. |
Null or empty input array
How to Handle:
Return 0 as no profit can be made without stock prices.
Input array with only one element
How to Handle:
Return 0 as a single day cannot result in a buy and sell transaction.
Input array with monotonically decreasing prices (always going down)
How to Handle:
Return 0 as there's no opportunity to buy low and sell high.
Input array with monotonically increasing prices (always going up)
How to Handle:
Calculate profit by buying on day 0 and selling on the last day, or accumulate profit from each increasing day.
Input array with all identical values
How to Handle:
Return 0 as there's no price difference to make a profit.
Integer overflow when accumulating profit with large price differences and many transactions
How to Handle:
Use a data type that can accommodate larger values (e.g., long) for profit accumulation to avoid overflow.
Input array contains very large price values (close to maximum integer)
How to Handle:
The algorithm should still work correctly as long as intermediate calculations don't overflow, address with larger data types if needed.
Alternating high and low prices creating many small profits
How to Handle:
The greedy approach of buying low and selling high on each increasing day handles this efficiently.
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
