Maximize Price Difference — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Iterating arrays and tracking min/max
O(n)O(1)Problem Description
Given an integer array prices where prices[i] denotes the stock price on day i, compute the greatest possible profit from a single transaction: buy on one day and sell on a later day. The transaction must respect the chronological order (buy index < sell index). If every later price is not higher than the purchase price, the maximum profit is 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximize Price Difference"
WHY DOES IT MATTER?
This pattern is essential because it teaches the fundamental technique of reducing a quadratic problem to linear time by maintaining a running state (in this case, the minimum price) that encapsulates all necessary information from previous elements. It is a cornerstone for more complex dynamic programming problems involving sequences and constraints.
OPTIMIZATION CHALLENGE
The key insight is that for any given sell day j, the best buy day is the day with the minimum price before j. Instead of recalculating the minimum for each j, we maintain a running minimum as we iterate through the array. This reduces the inner loop from O(n) to O(1), resulting in an overall O(n) solution.
REAL-WORLD CONNECTION
In financial trading systems, this algorithm is used to calculate the maximum potential profit from a single trade in a historical price series. It is also analogous to finding the maximum gain in a time-series signal, such as in network latency monitoring or sensor data analysis, where you want to identify the largest positive deviation from a previous baseline.
During the interview, explicitly state that you are maintaining a 'running minimum' to avoid the O(n^2) complexity. Emphasize that the chronological constraint (buy before sell) is what allows this optimization, as it ensures that the minimum price considered is always from a previous day.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of maximizing price difference is a classic instance of the "maximum subarray" or "maximum difference with order constraint" problem. The naive approach involves checking every possible pair of indices (i, j) where i < j, calculating prices[j] - prices[i], and keeping track of the maximum. This results in a time complexity of O(n^2), which becomes computationally infeasible for large arrays (e.g., n = 10^5 or 10^6) due to the quadratic growth in operations. This highlights the importance of recognizing that we do not need to compare every pair, but rather optimize the search space by leveraging the chronological constraint.
Interview Questions on This Problem
Q1How would you modify the solution to handle a scenario where you can make at most two transactions?
You can use dynamic programming with states representing the number of transactions completed and whether you are holding a stock. Alternatively, you can compute the maximum profit for one transaction ending at each day and starting at each day, then combine them to find the best two non-overlapping transactions. This typically results in O(n) time and O(n) or O(1) space depending on implementation.
Q2What if the array is circular, meaning you can buy on day n and sell on day 1?
For a circular array, you need to consider two cases: the best transaction that does not wrap around (standard problem) and the best transaction that wraps around. The wrapping case can be transformed into finding the minimum of (total sum - maximum subarray sum) or by duplicating the array and applying Kadane's algorithm with constraints. However, for stock prices, it's often simpler to handle the wrap-around by checking the best buy in the second half and best sell in the first half, or by using a modified DP approach.
Q3How would you optimize memory usage if the array is streamed in real-time and you cannot store the entire array?
You can solve this in O(1) space by maintaining only two variables: the minimum price seen so far and the maximum profit seen so far. As each new price arrives, update the minimum price if the current price is lower, and update the maximum profit if the difference between the current price and the minimum price is greater than the current maximum profit. This allows for real-time processing without storing the entire history.
Examples
Input
[7,1,5,3,6,4]
Output
5
Explanation: Buy on day 1 (price 1), sell on day 4 (price 6), profit = 6-1 = 5, which is the largest achievable.
Input
[2,4,1]
Output
2
Explanation: Buy on day 0 (price 2), sell on day 1 (price 4), profit = 2. No later sell yields higher profit.
Input
[9,7,4,3,1]
Output
0
Explanation: Prices continuously decline, so any buy‑sell pair would lose money; the algorithm returns 0.
Constraints
- 1 <= prices.length <= 200000
- -10^9 <= prices[i] <= 10^9
Optimal Approach & Strategy
Iterate through the array once, maintaining a variable for the minimum price seen so far. For each price, calculate the profit by subtracting the minimum price from the current price, and update the maximum profit if the current profit is higher.
Brute Force Approach
Use two nested loops to iterate over all pairs of indices (i, j) where i < j. Calculate the difference prices[j] - prices[i] and keep track of the maximum difference found.
Code Solutions
function maxProfit(prices){
let minPrice = Infinity;
let maxProf = 0;
for(const p of prices){
if(p < minPrice) minPrice = p;
else if(p - minPrice > maxProf) maxProf = p - minPrice;
}
return maxProf;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) process.exit(0);
const n = data[0];
const prices = data.slice(1,1+n);
console.log(maxProfit(prices));#include <bits/stdc++.h>
using namespace std;
int maxProfit(const vector<int>& prices){
int minPrice = INT_MAX;
int maxProf = 0;
for(int p:prices){
if(p<minPrice) minPrice=p;
else if(p-minPrice>maxProf) maxProf=p-minPrice;
}
return maxProf;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> prices(n);
for(int i=0;i<n;++i) cin>>prices[i];
cout<<maxProfit(prices);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int maxProfit(int[] prices){
int minPrice = Integer.MAX_VALUE;
int maxProf = 0;
for(int p:prices){
if(p < minPrice) minPrice = p;
else if(p - minPrice > maxProf) maxProf = p - minPrice;
}
return maxProf;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] prices = new int[n];
int idx = 0;
while(idx < n){
while(st.hasMoreTokens() && idx < n){
prices[idx++] = Integer.parseInt(st.nextToken());
}
if(idx==n) break;
line = br.readLine();
if(line==null) break;
st = new StringTokenizer(line);
}
System.out.println(maxProfit(prices));
}
}def max_profit(prices):
min_price = float('inf')
max_prof = 0
for p in prices:
if p < min_price:
min_price = p
else:
profit = p - min_price
if profit > max_prof:
max_prof = profit
return max_prof
if __name__=="__main__":
import sys
nums=list(map(int,sys.stdin.read().strip().split()))
if not nums:
sys.exit()
n=nums[0]
prices=nums[1:1+n]
print(max_profit(prices))function maxProfit(prices){
let minPrice = Infinity;
let maxProf = 0;
for(const p of prices){
if(p < minPrice) minPrice = p;
else if(p - minPrice > maxProf) maxProf = p - minPrice;
}
return maxProf;
}
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) process.exit(0);
const n = data[0];
const prices = data.slice(1,1+n);
console.log(maxProfit(prices));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.