Crack the Backend

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing one day to buy and a different day in the future to sell. Return the maximum profit you can achieve. If you cannot achieve any profit, return 0.

You may complete at most one transaction (one buy, one sell). Buy must occur before sell. So for each day we can consider selling on that day; the best buy would have been on the day with the minimum price so far.

Key Observations

For each day i (as a potential sell day), the best buy day is the day before i with the smallest price. So we maintain the minimum price seen so far and at each day compute profit = prices[i] - minPrice. The maximum of these profits is the answer.
One pass: minPrice = infinity, maxProfit = 0. For each price: maxProfit = max(maxProfit, price - minPrice), minPrice = min(minPrice, price). O(n) time, O(1) space.

Approach

High-level: minPrice = very large, maxProfit = 0. For each price in prices: update maxProfit = max(maxProfit, price - minPrice), then minPrice = min(minPrice, price). Return maxProfit.

Steps:

int minPrice = Integer.MAX_VALUE, maxProfit = 0. For each prices[i]: maxProfit = Math.max(maxProfit, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]).
Return maxProfit.

Implementation

Java

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;

    for (int p : prices) {
        maxProfit = Math.max(maxProfit, p - minPrice);
        minPrice = Math.min(minPrice, p);
    }

    return maxProfit;
}

Test Cases

Example 1

Input

prices = [7,1,5,3,6,4]

Expected

5

Explanation

Buy 1, sell 6.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

Multiple transactions (greedy: sum all rises); at most 2 transactions (DP).