Best Time to Buy and Sell Stock
Buying and Selling Stocks Problem – Hard Level Problem
You are given an array prices, where each element prices[i] represents the price of PrepCoin on the i-th day.
Your task is to determine the maximum profit you can make by selecting one day to buy a PrepCoin and another day after it to sell.
If it’s not possible to make any profit (e.g., prices are decreasing every day), you should return 0. This means you can also choose not to make any transactions.
Output: 6
Explanation : Buy prices[1] and sell prices[4], profit = 7 – 1 = 6.
Output: 0
Explanation : No profitable transactions can be made, thus the max profit is 0.
Constraints:
- 1 <= prices.length <= 100
- 0 <= prices[i] <= 100
Buying and Selling Stocks Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force approach involves iterating through the array with index i, treating it as the buying day, and checking all possible selling options on the days after i. This results in a time complexity of O(n²). Can you think of a more efficient solution?
Hint 2 :
You should buy at a price and always sell at a higher price. Can you iterate through the array with index i, considering it as either the buying price or the selling price?
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Two Pointers Method
- Dynamic Programming Method
1. Brute Force Method
This method check all possible pairs of days to calculate the maximum profit by iterating through every possible buy and sell combination. This approach has a time complexity of O(n^2).
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
int maxProfit(vector& prices) {
int res = 0;
for (int i = 0; i < prices.size(); i++) {
int buy = prices[i];
for (int j = i + 1; j < prices.size(); j++) {
int sell = prices[j];
res = max(res, sell - buy);
}
}
return res;
}
};
public class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for (int i = 0; i < prices.length; i++) {
int buy = prices[i];
for (int j = i + 1; j < prices.length; j++) {
int sell = prices[j];
res = Math.max(res, sell - buy);
}
}
return res;
}
}
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(len(prices)):
buy = prices[i]
for j in range(i + 1, len(prices)):
sell = prices[j]
res = max(res, sell - buy)
return res
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
let res = 0;
for (let i = 0; i < prices.length; i++) {
let buy = prices[i];
for (let j = i + 1; j < prices.length; j++) {
let sell = prices[j];
res = Math.max(res, sell - buy);
}
}
return res;
}
}
2. Two Pointers Method
Use a single pass with two variables to track the minimum price so far and the maximum profit, updating them as you traverse the array. This has a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int maxProfit(vector& prices) {
int l = 0, r = 1;
int maxP = 0;
while (r < prices.size()) {
if (prices[l] < prices[r]) {
int profit = prices[r] - prices[l];
maxP = max(maxP, profit);
} else {
l = r;
}
r++;
}
return maxP;
}
};
public class Solution {
public int maxProfit(int[] prices) {
int l = 0, r = 1;
int maxP = 0;
while (r < prices.length) {
if (prices[l] < prices[r]) {
int profit = prices[r] - prices[l];
maxP = Math.max(maxP, profit);
} else {
l = r;
}
r++;
}
return maxP;
}
}
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1
maxP = 0
while r < len(prices):
if prices[l] < prices[r]:
profit = prices[r] - prices[l]
maxP = max(maxP, profit)
else:
l = r
r += 1
return maxP
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
let l = 0, r = 1;
let maxP = 0;
while (r < prices.length) {
if (prices[l] < prices[r]) {
let profit = prices[r] - prices[l];
maxP = Math.max(maxP, profit);
} else {
l = r;
}
r++;
}
return maxP;
}
}
3. Dynamic Programming Method
This method maintain a table or array to store intermediate results, such as the minimum price up to a given day and the maximum profit calculated so far, optimizing computation over multiple traversals. Time complexity is O(n).
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int maxProfit(vector& prices) {
int maxP = 0;
int minBuy = prices[0];
for (int& sell : prices) {
maxP = max(maxP, sell - minBuy);
minBuy = min(minBuy, sell);
}
return maxP;
}
};
public class Solution {
public int maxProfit(int[] prices) {
int maxP = 0;
int minBuy = prices[0];
for (int sell : prices) {
maxP = Math.max(maxP, sell - minBuy);
minBuy = Math.min(minBuy, sell);
}
return maxP;
}
}
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxP = 0
minBuy = prices[0]
for sell in prices:
maxP = max(maxP, sell - minBuy)
minBuy = min(minBuy, sell)
return maxP
class Solution {
/**
* @param {number[]} prices
* @return {number}
*/
maxProfit(prices) {
let maxP = 0;
let minBuy = prices[0];
for (let sell of prices) {
maxP = Math.max(maxP, sell - minBuy);
minBuy = Math.min(minBuy, sell);
}
return maxP;
}
}
