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;
}
}
More Articles
121. Best Time to Buy and Sell Stock Leetcode Solution
Best Time to Buy and Sell Stock Leetcode Problem :
You are given an array prices where prices[i] is the price of a given stock on the ith 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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Best Time to Buy and Sell Stock Leetcode Solution :
Constraints :
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
Example 1:
- Input: prices = [7,6,4,3,1]
- Output: 0
Approach :
1)We make 2 extra arrays, left and right
2)We initialize the first element of left array as the first element of prices
3)We initialize the last element of right array as the last element of prices
4)To get the maximum Profit, we need minimum from left array and maximum from right array.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int maxProfit(vector< int>& prices) {
int n=prices.size();
int l[n],r[n];
l[0]=prices[0];
r[n-1]=prices[n-1];
for(int i=1;i< n;i++){
l[i]=min(l[i-1],prices[i]);
}
for(int i=n-2;i>=0;i--){
r[i]=max(r[i+1],prices[i]);
}
int maxProfit=0;
for(int i=0;i< n;i++){
maxProfit=max(maxProfit,r[i]-l[i]);
}
return maxProfit;
}
};
class Solution {
public int maxProfit(int[] prices) {
int min_price = prices[0];
int maxprof = 0;
for(int i=1;i< prices.length;i++){
maxprof = Math.max(maxprof,prices[i]-min_price);
min_price = Math.min(prices[i],min_price);
}
return maxprof;
}
}class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
max_profit = max(max_profit, price - min_price)
min_price = min(min_price, price)
return max_profit
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Best time to buy and Sell stock in Python
Best time to buy and Sell stock in Python
On this page, we will learn to create a Program to find Best time to buy and Sell stock in Python programing language.
Example:
- Input: [70, 150, 230, 280, 10, 505, 665]
- Output: We can make a maximum profit of 655
- Explanation: For the given set of stock prices we can make a maximum profit of 655 by buying the stock on day 4 & selling it on day 6
Problem Statement
The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days.
Rules
- We are allowed to buy and sell only once
- We can not sell before buying the stock
If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.
For example, if the given array is [70, 150, 230, 280, 10, 505, 665], the maximum profit of 655 can be earned by buying on day 4, selling on day 6.
Algorithm
- Initialize a variable to store profit (pro)
- Iterate using a for loop between 0 to one less then length of input array
- Run a nested for loop from range i+1 to length of array
- If arr[j] – arr[i] is greater then pro then change the value of pro to arr[j] – arr[i]
- After the loop ends pro stores the required answer
Python Code
def profit(arr):
pro = 0
for i in range(len(arr) - 1):
for j in range(i + 1, len(arr)):
if arr[j] - arr[i] > pro:
pro = arr[j] - arr[i]
return pro
array = [70, 150, 230, 280, 10, 505, 665]
print("We can make maximum profit of", profit(array))
Output
We can make maximum profit of 655
For similar question click on given button.
Login/Signup to comment