Optimizing Portfolio Returns — Problem Statement & Solution Guide
Problem Description
Given an array nums of integers where nums[i] denotes the price of a single stock on day i, determine the maximum profit achievable from exactly one buy‑sell transaction. The purchase must occur on a day strictly before the sale. If no transaction yields a positive profit, return 0. The solution must run in O(n) time and use O(1) additional space.
The input consists of a single line containing the array in standard JSON array notation. The output is a single integer representing the maximum profit.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimizing Portfolio Returns"
WHY DOES IT MATTER?
The running minimum pattern reduces a quadratic search to linear time, making the solution scalable to millions of days and essential for real‑time analytics.
OPTIMIZATION CHALLENGE
The key insight is that only the smallest price seen so far can contribute to the maximum profit for any future day, eliminating the need to store all past prices.
REAL-WORLD CONNECTION
In high‑frequency trading systems, a single pass over tick data with constant memory is critical to meet latency constraints, mirroring this algorithmic pattern.
When explaining this in an interview, emphasize the invariant: "minPrice is the lowest price up to the current index" and show how it guarantees optimality.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The goal is to find the maximum difference between two array elements where the larger element comes after the smaller one. A naive O(n^2) solution examines every pair of days, which becomes prohibitively slow for large inputs. The optimal strategy keeps a running minimum price while iterating once through the array, computing the profit if the current price were sold, and updating the maximum profit accordingly. This single-pass, constant‑space approach is a classic example of the "running minimum" pattern, which appears in many streaming, dynamic programming, and stock‑trading problems.
Interview Questions on This Problem
Q1How would you modify the algorithm to allow multiple buy‑sell transactions for maximum profit?
Maintain a running minimum and add any positive difference to a cumulative sum; this yields the maximum profit with unlimited transactions.
Q2What changes if the array contains negative prices (e.g., stock splits or dividends)?
The algorithm still works; the running minimum will capture the lowest negative price, and the profit calculation remains valid, but you must ensure the final answer is capped at zero if all differences are negative.
Q3Can you explain why the algorithm fails if you update the minimum after computing the profit?
Updating the minimum after computing profit would incorrectly allow selling at the same day you bought, violating the strictly before rule and potentially missing better future profits.
Examples
Input
[7,1,5,3,6,4]
Output
5
Explanation: Track the lowest price seen so far and the best profit. Day 0: price=7, min=7, profit=0 Day 1: price=1, min=1, profit=0 Day 2: price=5, profit=max(0,5-1)=4 Day 3: price=3, profit=max(4,3-1)=4 Day 4: price=6, profit=max(4,6-1)=5 Day 5: price=4, profit=max(5,4-1)=5 Maximum profit is 5.
Input
[7,6,4,3,1]
Output
0
Explanation: Prices are monotonically decreasing. Day 0: price=7, min=7, profit=0 Day 1: price=6, min=6, profit=0 Day 2: price=4, min=4, profit=0 Day 3: price=3, min=3, profit=0 Day 4: price=1, min=1, profit=0 No positive profit can be made, so output 0.
Constraints
- 1 <= prices.length <= 200000
- -10^9 <= prices[i] <= 10^9
- Time complexity O(n)
- Auxiliary space O(1)
Optimal Approach & Strategy
Traverse once, keep the minimum price seen so far and the maximum profit. For each price, update profit = price - minPrice, update maxProfit if higher, then update minPrice if current price is lower. This runs in O(n) time and O(1) space.
Brute Force Approach
Check every pair of days, compute the profit if buying before selling, and keep the maximum. This takes O(n^2) time and O(1) space.
Verified Code Solutions
const nums = [7,1,5,3,6,4]; // Example input
let minPrice = Infinity;
let maxProfit = 0;
for(const price of nums){
if(price < minPrice) minPrice = price;
else if(price - minPrice > maxProfit) maxProfit = price - minPrice;
}
console.log(maxProfit);#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> nums = {7,1,5,3,6,4}; // Example input
int minPrice = INT_MAX;
int maxProfit = 0;
for(int price : nums){
if(price < minPrice) minPrice = price;
else if(price - minPrice > maxProfit) maxProfit = price - minPrice;
}
cout << maxProfit;
return 0;
}import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] nums = {7,1,5,3,6,4}; // Example input
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for(int price : nums){
if(price < minPrice) minPrice = price;
else if(price - minPrice > maxProfit) maxProfit = price - minPrice;
}
System.out.println(maxProfit);
}
}nums = [7,1,5,3,6,4] # Example input
min_price = float('inf')
max_profit = 0
for price in nums:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
print(max_profit)const nums = [7,1,5,3,6,4]; // Example input
let minPrice = Infinity;
let maxProfit = 0;
for(const price of nums){
if(price < minPrice) minPrice = price;
else if(price - minPrice > maxProfit) maxProfit = price - minPrice;
}
console.log(maxProfit);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.