Explorer
Data Structures & Algorithms

Find the maximum single-trade profit from stock prices given over time.

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 a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`.

Examples

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

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

Input: prices = [7, 6, 4, 3, 1]

Output: 0

Explanation: Combining the input according to Stock Buy and Sell logic yields 0.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: You must buy before you can sell. šŸ’” Hint 2: Keep track of the lowest stock price seen so far as you iterate. šŸ’” Hint 3: At each day, calculate profit = price - minPrice and update maxProfit if higher.

Editorial & Approach

Problem Overview & Intuition

To maximize profit with a single transaction, sell on day i at price prices[i] while having bought at the lowest price among days 0 to i - 1. A single pass maintaining minPrice accomplishes this in O(N) time.

Step-by-Step Approach

  1. Initialize minPrice = Infinity and maxProfit = 0.
  2. Iterate through each price in prices.
  3. If price < minPrice, update minPrice = price.
  4. Else if price - minPrice > maxProfit, update maxProfit = price - minPrice.
  5. Return maxProfit.

Optimal Implementation (JavaScript)

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (let price of prices) {
    if (price < minPrice) {
      minPrice = price;
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice;
    }
  }
  return maxProfit;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass through prices.
Space Complexity O(1) ā€” two tracking variables.

Edge Cases & Corner Traps Handled

  • Strictly decreasing prices: profit is 0.
  • Single day prices array: profit is 0.
  • All identical prices: profit is 0.

Stock Buy and Sell

Medium
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 a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`.
Example Scenarios
1Example 1
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation:

Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

2Example 2
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation:

Combining the input according to Stock Buy and Sell logic yields 0.

Editor
Loading Editor...
prices =
[7, 1, 5, 3, 6, 4]
Output:Click "Run" above to execute and verify your code here.
5