Definition
- Best Time to Buy and Sell Stock – find the maximum profit from one buy followed by one later sell.
- Running minimum – track the minimum price seen so far as you scan forward.
- Profit calculation – at each day,
profit = price[i] - minSoFar; updatemaxProfitif larger. - No-loss encoding – initialise
maxProfitto zero so the answer is zero if prices only fall. - Complexity – O(n) time, O(1) space, replacing the O(n squared) all-pairs approach.
- Variant awareness – this solves single-transaction only; multi-transaction needs DP.
Rajesh follows a share on the National Bank of India trading app and wants the most he could have made by buying on one day and selling on a later day. Walking through the days once, he remembers the cheapest price seen so far and on each day asks: if I had bought at that cheapest price and sold today, how much would I make? He keeps the biggest such gain.
Understanding the Concepts
What is the Best Time to Buy and Sell Stock problem?
Given an array of daily prices, find the maximum profit from one buy and one later sell. You must buy before you sell. If no profit is possible, return zero. This is a single-transaction problem with an elegant single-pass solution.
package com.bank.service;
import java.math.BigDecimal;
public class BestTimeToBuySell {
public BigDecimal maxProfit(BigDecimal[] prices) {
if (prices == null || prices.length < 2) return BigDecimal.ZERO;
BigDecimal minPrice = prices[0];
BigDecimal maxProfit = BigDecimal.ZERO;
for (int i = 1; i < prices.length; i++) {
BigDecimal profit = prices[i].subtract(minPrice);
if (profit.compareTo(maxProfit) > 0) maxProfit = profit;
if (prices[i].compareTo(minPrice) < 0) minPrice = prices[i];
}
return maxProfit;
}
}
Why does the single-pass approach work?
For any selling day, the best buying day is the cheapest day at or before it. You do not need to compare every pair: just remember the minimum price seen so far. This reduces the naive O(n squared) double loop to a single O(n) pass.
package com.bank.service;
public class SinglePassExplained {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int profit = prices[i] - minPrice;
maxProfit = Math.max(maxProfit, profit);
minPrice = Math.min(minPrice, prices[i]);
System.out.println("Day " + i + ": price=" + prices[i]
+ " min=" + minPrice + " profit=" + profit
+ " best=" + maxProfit);
}
}
}
Day 1: price=1 min=1 profit=-6 best=0
Day 2: price=5 min=1 profit=4 best=4
Day 3: price=3 min=1 profit=2 best=4
Day 4: price=6 min=1 profit=5 best=5
Day 5: price=4 min=1 profit=3 best=5
Why initialise maxProfit to zero?
Initialising to zero encodes the rule that you may choose not to trade. If prices only fall, the answer is zero (no profit) rather than a negative loss. If the problem requires exactly one transaction even at a loss, you would initialise to Integer.MIN_VALUE instead.
// Default: not forced to trade (maxProfit starts at 0)
int maxProfit = 0; // no trade -> profit is 0
// Variant: must trade (maxProfit starts at MIN_VALUE)
int maxProfit = Integer.MIN_VALUE; // forces finding the best trade
// Prices: [5, 4, 3, 2, 1]
// Default: maxProfit = 0 (no profitable trade)
// Variant: maxProfit = -1 (best loss is selling at 2, bought at 3)
What is the time and space complexity?
One pass through the array with constant work per element gives O(n) time. Two variables (minPrice and maxProfit) give O(1) space.
- Time – O(n), one pass through the prices.
- Space – O(1), two tracking variables.
- Comparison – the brute-force approach checks all O(n squared) pairs.
// Brute force: O(n^2)
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
// Optimised: O(n)
for (int i = 1; i < n; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
How is this different from the multi-transaction variant?
The single-transaction version allows only one buy and one sell. The multi-transaction variant (Buy and Sell Stock II) allows unlimited transactions. The at-most-K variant requires state-machine DP.
| Variant | Transactions | Strategy | Complexity |
|---|---|---|---|
| I (single) | Exactly 1 | Min-price tracking | O(n) time, O(1) space |
| II (unlimited) | Unlimited | Sum all gains | O(n) time, O(1) space |
| III (at most 2) | At most 2 | State machine DP | O(n) time, O(1) space |
| IV (at most K) | At most K | 2K-state DP | O(nK) time, O(K) space |
// Variant II: unlimited transactions
int profit = 0;
for (int i = 1; i < n; i++)
if (prices[i] > prices[i - 1])
profit += prices[i] - prices[i - 1];
What are the edge cases?
Edge cases include a single-element array (cannot trade), an empty array, monotonically decreasing prices (profit is zero), and monotonically increasing prices (buy on day 1, sell on last day).
package com.bank.service;
public class StockEdgeCases {
public static void main(String[] args) {
// Single element
System.out.println(maxProfitInt(new int[]{5})); // 0
// All decreasing
System.out.println(maxProfitInt(new int[]{5,4,3,2,1})); // 0
// All increasing
System.out.println(maxProfitInt(new int[]{1,2,3,4,5})); // 4
// Valley then peak
System.out.println(maxProfitInt(new int[]{3,1,4})); // 3
}
static int maxProfitInt(int[] prices) {
if (prices.length < 2) return 0;
int min = prices[0], best = 0;
for (int i = 1; i < prices.length; i++) {
best = Math.max(best, prices[i] - min);
min = Math.min(min, prices[i]);
}
return best;
}
}
0
0
4
3
What are common mistakes?
The most common mistake is computing maxProfit before updating minPrice in the same iteration, which can cause using today's price as both buy and sell. Another mistake is not using BigDecimal for money calculations.
// WRONG: update min first, then compute profit
minPrice = Math.min(minPrice, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
// This allows buying and selling on the same day!
// CORRECT: compute profit first, then update min
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
// Buy must be before sell
How would you apply this in a banking system?
At the National Bank of India, Rajesh's trading app shows the best single buy-then-sell profit over a price window. The app uses BigDecimal for exact money arithmetic and returns zero when the share only falls.
package com.bank.service;
import java.math.BigDecimal;
public class BacktestService {
public BigDecimal bestSingleTrade(BigDecimal[] dailyPrices) {
if (dailyPrices == null || dailyPrices.length < 2)
return BigDecimal.ZERO;
BigDecimal minPrice = dailyPrices[0];
BigDecimal bestProfit = BigDecimal.ZERO;
for (int i = 1; i < dailyPrices.length; i++) {
BigDecimal profit = dailyPrices[i].subtract(minPrice);
if (profit.compareTo(bestProfit) > 0) bestProfit = profit;
if (dailyPrices[i].compareTo(minPrice) < 0)
minPrice = dailyPrices[i];
}
return bestProfit;
}
}
What should a senior engineer know?
A senior engineer should immediately clarify which variant is being asked. They should use BigDecimal for financial calculations. They should also know that this problem is equivalent to finding the maximum subarray sum of the daily price differences (Kadane's algorithm on the diff array).
// Kadane equivalence:
// diff[i] = prices[i] - prices[i-1]
// maxProfit = max subarray sum of diff[]
// This is because profit from buy at day a to sell at day b
// = sum of diff[a+1] + diff[a+2] + ... + diff[b]
int maxEndingHere = 0, maxSoFar = 0;
for (int i = 1; i < prices.length; i++) {
maxEndingHere = Math.max(0, maxEndingHere + prices[i] - prices[i-1]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
Visual Overview
Prices: [7, 1, 5, 3, 6, 4]
Day: 0 1 2 3 4 5
Price: 7 1 5 3 6 4
Min: 7 1 1 1 1 1
Profit: - -6 4 2 5 3
Best: 0 0 4 4 5 5
↑
maxProfit = 5
(buy at 1, sell at 6)
┌────────────────────────────────────────┐
│ Day 0: min=7, no sell yet │
│ Day 1: price=1 < 7, update min=1 │
│ Day 2: 5-1=4 > 0, best=4 │
│ Day 3: 3-1=2 < 4, best stays 4 │
│ Day 4: 6-1=5 > 4, best=5 ← ANSWER │
│ Day 5: 4-1=3 < 5, best stays 5 │
└────────────────────────────────────────┘
Key Takeaway
Best Time to Buy and Sell Stock asks for the maximum profit from one buy and one later sell. The single-pass solution tracks two variables: the minimum price seen so far and the best profit seen so far. For each day, I compute the profit if I sold today against the cheapest earlier price and update the best, then I update the running minimum.
The design choice I always call out is initialising the best profit to zero, which means I am not forced to trade. If prices only fall, the answer is zero rather than a loss. I also clarify that this is the single-transaction version, since multi-transaction and at-most-K variants need DP.
For financial calculations, I use BigDecimal to keep money exact, comparing with compareTo and subtracting with the subtract method. The common mistake is updating the minimum before computing the profit, which allows buying and selling on the same day.
At the National Bank of India, I used this in Rajesh's trading app backtest, computing the best single buy-then-sell profit over a price window quickly and never suggesting a buy after a sell.
Remember one sentence: track the running minimum price, and at each day the profit is today's price minus that minimum.
---