Max Profit

You are twenty minutes into a Bloomberg phone screen when the interviewer says, "Let's say you have historical stock prices for FAANG over the past week. You can make exactly one trade. How do you maximize your profit?" This problem, widely known as Best Time to Buy and Sell Stock, is a staple of the Blind 75 and one of the most frequently asked array questions at companies like Bloomberg, Microsoft, and LinkedIn. It looks simple, but it separates candidates who reach for nested loops from those who recognize a clean single-pass pattern.

TL;DR

Track two values as you scan the price array left to right: the minimum price seen so far (your ideal buy point) and the maximum profit found so far. At each price, check if selling at that price beats your current best profit. If the current price is lower than the running minimum, update the minimum. One pass, O(n) time, O(1) space.

Why This Problem Matters

The stock profit problem is a gateway to greedy algorithm thinking. Instead of exhaustively comparing every possible buy-sell pair (O(n^2)), you exploit the constraint that you must buy before you sell. That single observation unlocks a linear-time solution. The same "track the best so far" pattern shows up in maximum subarray (Kadane's algorithm), trapping rain water, and dozens of other interview favorites.

Understanding the Problem

You're given an array of n integers, with each integer representing the closing price of ticker FAANG on a particular day. Write a method that returns the maximum profit possible if you buy and sell exactly one stock, exactly once. You must buy before you sell. If no profit is possible, return 0.

maxProfit([30, 25, 20, 15]) -> 0
maxProfit([50, 0, 10, 100]) -> 100
maxProfit([30, 50, 10, 100]) -> 90

Constraints

• The input array will always contain at least two integers (2 ≤ n ≤ 10,000)
• Stock prices are non-negative integers (0 ≤ price ≤ 10,000)
• You must buy before you sell

Edge Cases

1. All decreasing prices: No profit is possible, return 0
2. All same prices: No profit, return 0
3. Monotonically increasing: Buy on day 1, sell on the last day
4. Best buy comes after an early profit opportunity: The algorithm must not lock in an early gain and miss a better one later

The Brute Force Trap

A naive approach uses nested loops: for every day i, check every later day j and compute prices[j] - prices[i]. Track the maximum. This works but runs in O(n^2) time. For 10,000 prices, that is 50 million comparisons. We can do much better.

Solution Approach

The key insight is that at any point in the array, the best profit you could earn by selling at the current price depends only on the lowest price you have seen so far. You do not need to look back at every previous price, just the minimum.

Here is the algorithm:

1. Set min to the first price and maxProfit to 0
2. Walk through the array starting at index 1
3. At each price, compute price - min. If this exceeds maxProfit, update maxProfit
4. If the current price is lower than min, update min
5. Return maxProfit

Tracing Through [50, 0, 10, 100]

The minimum drops to 0 on day 2. When we reach price 100 on day 4, the profit is 100 - 0 = 100. That is our answer.

The Tricky Case: [30, 50, 10, 100]

At price 50, we see a profit of 20 (50 - 30). But then the price drops to 10, updating our minimum. When we hit 100, the profit is 90 (100 - 10), which beats the earlier 20. The algorithm naturally picks the better trade without any backtracking.

Declining Market: [100, 99, 98, 95]

Every price is lower than the last. No sell price minus the running minimum ever exceeds 0, so maxProfit stays at 0. No special case logic needed.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public int maxProfit(int[] prices) {
    int min = prices[0], maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min;
      }
      if (prices[i] < min) {
        min = prices[i];
      }
    }
    return maxProfit;
  }
}

Let's walk through the logic:

1. Initialize: min starts at the first price (our initial "buy" candidate) and maxProfit starts at 0 (the worst case)
2. Check profit: At each price, prices[i] - min is the profit we would earn if we bought at min and sold now. If it beats our record, update maxProfit
3. Update minimum: If the current price is lower than min, this becomes our new best buy candidate for future days
4. Return: After one pass, maxProfit holds the answer

The order of the two checks matters. We check profit before updating min so we never buy and sell on the same day. This is also why both checks use separate if statements rather than if/else: a price can simultaneously produce a new best profit AND not be a new minimum, or it can be a new minimum that produces no profit.

Complexity Analysis

Time: O(n) where n is the number of prices. We scan the array once, doing constant work at each element.

Space: O(1). We use two variables (min and maxProfit) regardless of input size. No extra arrays, no hash maps, no recursion stack.

Why Not Sort?

Sorting would let you find the overall min and max, but it destroys the ordering information. The minimum must come before the maximum in the original array. Sorting loses that relationship. Even if you tracked original indices, sorting costs O(n log n), which is worse than our O(n) solution.

Common Pitfalls

1. Checking profit after updating min: If you update min first, you might compute a profit of 0 (selling at the same price you just "bought"). Always check profit before updating the minimum.

2. Using global min and max: Finding the array minimum and maximum separately ignores ordering. The min might appear after the max, making that trade impossible.

3. Returning a negative profit: The problem asks you to return 0 if no profit is possible. By initializing maxProfit to 0, you handle this automatically.

4. Off-by-one on the loop: Start at index 1 since min is initialized to prices[0]. Starting at 0 is harmless but wastes a comparison.

Interview Tips

When presenting this solution:

• Start by acknowledging the O(n^2) brute force, then explain why it is unnecessary
• State the key insight clearly: "I only need the minimum price seen so far to compute the best profit at any given day"
• Mention that maxProfit initialized to 0 handles the no-profit case automatically
• If asked about multiple transactions, explain that the problem changes: you would sum all positive consecutive differences instead

Common follow-ups:

• "What if you can make at most k transactions?" (Dynamic programming, O(nk) time)
• "What if you can make unlimited transactions?" (Sum all positive day-to-day differences)
• "What if there's a cooldown period between transactions?" (State machine DP)

Key Takeaways

• Track the running minimum and maximum profit in a single left-to-right pass for O(n) time and O(1) space.
• Always check profit before updating the minimum to ensure you never buy and sell on the same day.
• Initializing maxProfit to 0 naturally handles declining markets without special case logic.
• The greedy "best so far" pattern generalizes to many array problems including Kadane's algorithm and trapping rain water.
• Do not sort the array or find the global min/max independently since ordering matters and those approaches either break correctness or cost more time.

Practice and Related Problems

Once you are comfortable with the single-transaction version, try these progressions:

• Maximum subarray sum (Kadane's algorithm, same "best so far" pattern)
• Best time to buy and sell stock with multiple transactions
• Best time to buy and sell stock with cooldown
• Trapping rain water (track max from both directions)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you're preparing for phone screens or on-site interviews, mastering greedy patterns like this one will set you up well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def max_profit(self, prices: List[int]) -> int:
        current_min = prices[0]
        max_profit = 0

        for i in range(1, len(prices)):
            if prices[i] - current_min > max_profit:
                max_profit = prices[i] - current_min
            if prices[i] < current_min:
                current_min = prices[i]
        return max_profit

JavaScript

class Solution {
  maxProfit(prices) {
    let min = prices[0], maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min;
      }
      if (prices[i] < min) {
        min = prices[i];
      }
    }
    return maxProfit;
  }
}

TypeScript

class Solution {
  maxProfit(prices: number[]): number {
    let min = prices[0], maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min;
      }
      if (prices[i] < min) {
        min = prices[i];
      }
    }
    return maxProfit;
  }
}

C++

#include <vector>

class Solution {
public:
  int maxProfit(std::vector<int> prices) {
    int min = prices[0], maxProfit = 0;

    for (int i = 1; i < prices.size(); i++) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min;
      }
      if (prices[i] < min) {
        min = prices[i];
      }
    }
    return maxProfit;
  }
};

Go

package solution

func (s *Solution) MaxProfit(prices []int) int {
	min, maxProfit := prices[0], 0

	for i := 1; i < len(prices); i++ {
		if (prices[i] - min) > maxProfit {
			maxProfit = prices[i] - min
		}
		if prices[i] < min {
			min = prices[i]
		}
	}
	return maxProfit
}

type Solution struct {
}

Scala

class Solution {
  def maxProfit(prices: Array[Int]): Int = {
    var min = prices(0)
    var maxProfit = 0

    for (i <- 1 until prices.length) {
      if ((prices(i) - min) > maxProfit) maxProfit = prices(i) - min
      if (prices(i) < min) min = prices(i)
    }
    maxProfit
  }
}

Kotlin

class Solution {

  fun maxProfit(prices: IntArray): Int {
    var min = prices[0]
    var maxProfit = 0

    for (i in 1 until prices.size) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min
      }
      if (prices[i] < min) {
        min = prices[i]
      }
    }
    return maxProfit
  }
}

Swift

import Foundation

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var minPrice = prices[0]
        var maxProfit = 0

        for i in 1..<prices.count {
            if (prices[i] - minPrice) > maxProfit {
                maxProfit = prices[i] - minPrice
            }
            if prices[i] < minPrice {
                minPrice = prices[i]
            }
        }
        return maxProfit
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn max_profit(&self, prices: Vec<i32>) -> i32 {
        let mut min = prices[0];
        let mut max_profit = 0;

        for i in 1..prices.len() {
            if (prices[i] - min) > max_profit {
                max_profit = prices[i] - min;
            }
            if prices[i] < min {
                min = prices[i];
            }
        }
        max_profit
    }
}

C#

public class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0], maxProfit = 0;

        for (int i = 1; i < prices.Length; i++) {
            if ((prices[i] - min) > maxProfit) {
                maxProfit = prices[i] - min;
            }
            if (prices[i] < min) {
                min = prices[i];
            }
        }
        return maxProfit;
    }
}

Dart

class Solution {
  int maxProfit(List<int> prices) {
    int min = prices[0], maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {
      if ((prices[i] - min) > maxProfit) {
        maxProfit = prices[i] - min;
      }
      if (prices[i] < min) {
        min = prices[i];
      }
    }
    return maxProfit;
  }
}

PHP

<?php

class Solution {
    public function maxProfit(array $prices): int {
        $min = $prices[0];
        $maxProfit = 0;

        for ($i = 1; $i < count($prices); $i++) {
            if (($prices[$i] - $min) > $maxProfit) {
                $maxProfit = $prices[$i] - $min;
            }
            if ($prices[$i] < $min) {
                $min = $prices[$i];
            }
        }
        return $maxProfit;
    }
}

Ruby

class Solution
  def max_profit(prices)
    min = prices[0]
    max_profit = 0

    prices[1..-1].each do |price|
      max_profit = price - min if (price - min) > max_profit
      min = price if price < min
    end

    max_profit
  end
end