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.
Examples
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 – 1 = 5.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
Approach 1 (Brute Force)
Initialize maxProfit = 0.
Use two nested loops:
- Outer loop picks a day
ito buy the stock. - Inner loop picks a day
j > ito sell the stock. - For every pair
(i, j), calculate the profit:prices[j] - prices[i]. - If this profit is greater than
maxProfit, updatemaxProfit.
Return maxProfit after all iterations.
Dry Run
Input: prices = [7, 1, 5, 3, 6, 4]
i = 0, prices[i] = 7
j = 1 → 1 - 7 = -6 → maxProfit = 0
j = 2 → 5 - 7 = -2 → maxProfit = 0
j = 3 → 3 - 7 = -4 → maxProfit = 0
j = 4 → 6 - 7 = -1 → maxProfit = 0
j = 5 → 4 - 7 = -3 → maxProfit = 0
i = 1, prices[i] = 1
j = 2 → 5 - 1 = 4 → maxProfit = 4
j = 3 → 3 - 1 = 2 → maxProfit = 4
j = 4 → 6 - 1 = 5 → maxProfit = 5
j = 5 → 4 - 1 = 3 → maxProfit = 5
i = 2, prices[i] = 5
j = 3 → 3 - 5 = -2 → maxProfit = 5
j = 4 → 6 - 5 = 1 → maxProfit = 5
j = 5 → 4 - 5 = -1 → maxProfit = 5
... and so on.
Final maxProfit = 5 (buy at 1, sell at 6)
Time and Space Complexity
- Time Complexity: O(n²)
Two nested loops. For every element i, check all j > i. Total comparisons = n(n-1)/2 → O(n²) - Space Complexity: O(1)
No extra data structures used. Only uses a variablemaxProfit.
var maxProfit = function(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
if ((prices[j] - prices[i]) > maxProfit) {
maxProfit = prices[j] - prices[i];
}
}
}
return maxProfit;
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
};
int maxProfit(int* prices, int pricesSize) {
int maxProfit = 0;
for (int i = 0; i < pricesSize; i++) {
for (int j = i + 1; j < pricesSize; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
public class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}
class Solution(object):
def maxProfit(self, prices):
maxProfit = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
profit = prices[j] - prices[i]
if profit > maxProfit:
maxProfit = profit
return maxProfit
public class Solution {
public int MaxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.Length; i++) {
for (int j = i + 1; j < prices.Length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
}
Approach 2 (Optimal)
- Initialize
minas the first price. - Initialize
maxProfitas 0. - Loop through the prices from index 1 to the end:
- If the current price minus min is greater than maxProfit, update maxProfit.
- If the current price is less than min, update min to this new lower value.
- Return
maxProfitat the end.
Dry Run
prices = [7, 1, 5, 3, 6, 4]
min = 7, maxProfit = 0
i = 1 → prices[1] = 1
1 < 7 → update min = 1
i = 2 → prices[2] = 5
5 - 1 = 4 > 0 → update maxProfit = 4
i = 3 → prices[3] = 3
3 - 1 = 2 < 4 → no change
i = 4 → prices[4] = 6
6 - 1 = 5 > 4 → update maxProfit = 5
i = 5 → prices[5] = 4
4 - 1 = 3 < 5 → no change
➡️ Final maxProfit = 5 ✅
Time and Space Complexity
- Time Complexity: O(n)
One loop through the prices array. - Space Complexity: O(1)
Only a few variables used (min,maxProfit).
var maxProfit = function(prices) {
let min = prices[0];
let maxProfit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] - min > maxProfit) {
maxProfit = prices[i] - min;
}
if (prices[i] < min) {
min = prices[i];
}
}
return maxProfit;
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min_price = prices[0];
int max_profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] - min_price > max_profit)
max_profit = prices[i] - min_price;
if (prices[i] < min_price)
min_price = prices[i];
}
return max_profit;
}
};
int maxProfit(int* prices, int pricesSize){
int min_price = prices[0];
int max_profit = 0;
for (int i = 1; i < pricesSize; i++) {
int profit = prices[i] - min_price;
if (profit > max_profit)
max_profit = profit;
if (prices[i] < min_price)
min_price = prices[i];
}
return max_profit;
}
class Solution {
public int maxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int profit = prices[i] - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
if (prices[i] < minPrice) {
minPrice = prices[i];
}
}
return maxProfit;
}
}
class Solution:
def maxProfit(self, prices):
min_price = prices[0]
max_profit = 0
for i in range(1, len(prices)):
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
if prices[i] < min_price:
min_price = prices[i]
return max_profit
public class Solution {
public int MaxProfit(int[] prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.Length; i++) {
int profit = prices[i] - minPrice;
if (profit > maxProfit)
maxProfit = profit;
if (prices[i] < minPrice)
minPrice = prices[i];
}
return maxProfit;
}
}
