How to get maximum profit by buying and selling a stock when at most one transaction is allowed?
In this problem, we have given an array of stock prices, the ith element represents the stock price on ith day.
If we are allowed 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.
Note that you cannot sell a stock before you buy one. If it’s not possible to achieve any profit return 0.
For example –
Example 1-
Input – { 9, 1, 6, 3, 7, 4}
Output – 6 (Buy on day 2 (1) and sell on day 5 (7))
Example 2-
Input – {5, 4, 3, 2, 1}
Output – 0 (It is not possible to do any transaction)
As per the problem statement only one transaction is allowed. So, we have to buy and sell in such a way so that we can get the maximum profit.
In this tutorial, i am going to explain multiple approaches to solve this problem. We will start with the brute force approach and then we’ll improve our solution to solve this problem efficiently.
Best Time to Buy and Sell Stock | At most one transaction is allowed
The simplest approach to solve this problem is to run two for loops. The inner loop (i) will start from 0th index and outer loop will start from i+1. Also, we have to sell the stock price at higher price to get the maximum profit.
For each iteration, check if the value present at j index is greater than i then update the value of maximum profit which keep track of max profit we get by buy and sell a stock.
The time complexity of this approach is O(n^2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/* Buy and sell stock to get maximum profit when at most one transaction is allowed. */ class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for(int i = 0; i < prices.length-1; i++) { for(int j = i+1; j < prices.length; j++) { //Sell at higher price if(prices[j] > prices[i]) { maxProfit = Math.max(maxProfit, prices[j] - prices[i]); } } } return maxProfit; } } |
Programming questions on arrays
Programming questions on linked list
Best Time to Buy and Sell Stock – Java Code
Let’s improve our previous solution. In our previous solution, we have used two for loops to solve this problem. Let’s discuss how we can solve them in a single iteration.
For this i have declared two variables one to keep minimum stock price and one to keep track of max profit. Then run a loop to iterate stock prices. Then at each step check the value present at current index is smaller than value present at min variable. If it’s assign the current index value in min variable then calculate the different between current index value and min value. Also, keep track of max profit.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int maxProfit(int[] prices) { int min = Integer.MAX_VALUE; int maxProfit = 0; for(int i = 0; i < prices.length; i++) { if(prices[i] < min) { min = prices[i]; } maxProfit = Math.max(maxProfit, prices[i]-min); } return maxProfit; } } |
