.png)
Stock Buy and Sell (Single Transaction)
Problem Statement
You are given an array prices[] where prices[i] represents the price of a stock on day i.
You are allowed to complete only one transaction:
- Buy on one day
- Sell on a later day
Find the maximum profit you can achieve.
If no profit is possible, return 0.
Example 1
Input
prices = [7, 1, 5, 3, 6, 4]
Output
5
Explanation
Buy on day 1 at price 1
Sell on day 4 at price 6
Profit = 6 - 1 = 5
Example 2
Input
prices = [7, 6, 4, 3, 1]
Output
0
Explanation
Prices are decreasing, so no profit is possible.
Why This Problem Is Important
- Very common interview question
- Tests understanding of:
- Minimum tracking
- Greedy strategy
- One-pass optimization
- Foundation for advanced stock problems
Approaches Overview
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Optimized (Greedy / Min Price Tracking) | O(n) | O(1) |
Approach 1: Brute Force Method
Idea
Try every possible buy day and every possible sell day after it, calculate profit, and track the maximum profit.
Algorithm
- Initialize maxProfit = 0
- For each day i:
- For each day j > i:
- Profit = prices[j] - prices[i]
- Update maxProfit
- For each day j > i:
- Return maxProfit
Time and Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6;
int maxProfit = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int profit = prices[j] - prices[i];
if(profit > maxProfit)
maxProfit = profit;
}
}
printf("Maximum Profit: %d", maxProfit);
return 0;
}
JavaScript Implementation
let prices = [7, 1, 5, 3, 6, 4];
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
let profit = prices[j] - prices[i];
if (profit > maxProfit)
maxProfit = profit;
}
}
console.log("Maximum Profit:", maxProfit);
Approach 2: Optimized Greedy Approach (One Pass)
Core Idea
- Track the minimum price so far
- At each day, calculate potential profit if sold today
- Update maximum profit accordingly
This ensures:
- Buy happens before sell
- Only one transaction
Algorithm
- Initialize:
- minPrice = prices[0]
- maxProfit = 0
- Traverse from day 1 to end:
- Update minPrice = min(minPrice, prices[i])
- Calculate profit = prices[i] - minPrice
- Update maxProfit
- Return maxProfit
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
#include<limits.h>
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6;
int minPrice = INT_MAX;
int maxProfit = 0;
for(int i = 0; i < n; i++) {
if(prices[i] < minPrice)
minPrice = prices[i];
int profit = prices[i] - minPrice;
if(profit > maxProfit)
maxProfit = profit;
}
printf("Maximum Profit: %d", maxProfit);
return 0;
}
C++ Implementation
#include<iostream>
#include<climits>
using namespace std;
int main() {
int prices[] = {7, 1, 5, 3, 6, 4};
int n = 6;
int minPrice = INT_MAX;
int maxProfit = 0;
for(int i = 0; i < n; i++) {
minPrice = min(minPrice, prices[i]);
maxProfit = max(maxProfit, prices[i] - minPrice);
}
cout << "Maximum Profit: " << maxProfit;
return 0;
}
Java Implementation
public class StockBuySell {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int price : prices) {
if(price < minPrice)
minPrice = price;
maxProfit = Math.max(maxProfit, price - minPrice);
}
System.out.println("Maximum Profit: " + maxProfit);
}
}
Python Implementation
prices = [7, 1, 5, 3, 6, 4]
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
print("Maximum Profit:", max_profit)
JavaScript Implementation
let prices = [7, 1, 5, 3, 6, 4];
let minPrice = Number.MAX_VALUE;
let maxProfit = 0;
for (let price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
console.log("Maximum Profit:", maxProfit);
Dry Run (Optimized Approach)
Prices: [7, 1, 5, 3, 6, 4]
Day | Price | MinPrice | Profit | MaxProfit
0 | 7 | 7 | 0 | 0
1 | 1 | 1 | 0 | 0
2 | 5 | 1 | 4 | 4
3 | 3 | 1 | 2 | 4
4 | 6 | 1 | 5 | 5
5 | 4 | 1 | 3 | 5
Key Interview Notes
- Selling must occur after buying
- Greedy approach ensures best result in one pass
- No extra memory needed
- Returns 0 if profit is negative
Summary
- Brute force checks all possibilities but is slow
- Optimized approach tracks minimum price
- Best solution runs in O(n) time
- Very frequently asked interview problem
Next Problems You Can Cover
Stock Buy and Sell (Multiple Transactions)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
