Best Time to Buy and Sell Stock

EasyArrayGreedySliding Window
Category: Sliding Window
Companies that ask this question:
AmazonFacebookMicrosoftBloombergGoogle

Approach

Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith 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

Example 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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

Approach

Intuition

The key insight is that we want to buy at the lowest price and sell at the highest price after that buy date. We can solve this in a single pass by keeping track of:

  1. The minimum price seen so far (best buy price)
  2. The maximum profit achievable so far

Algorithm

  1. Initialize minPrice to infinity and maxProfit to 0
  2. For each price in the array:
    • Update minPrice if current price is lower
    • Calculate potential profit: currentPrice - minPrice
    • Update maxProfit if this profit is higher
  3. Return maxProfit

This is essentially a sliding window or greedy approach where we track the best opportunity as we scan through the array.

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(1) - Only using two variables

Pattern Recognition

This problem demonstrates:

  • Greedy approach: Making locally optimal choices (tracking minimum price)
  • Sliding window: Conceptually maintaining a window from min price to current price
  • Array scanning: Single pass with state tracking

Solution

java
1class Solution {
2    public int maxProfit(int[] prices) {
3        // Track the minimum price seen so far
4        int minPrice = Integer.MAX_VALUE;
5        // Track the maximum profit achievable
6        int maxProfit = 0;
7
8        // Single pass through the array
9        for (int price : prices) {
10            // Update minimum price if current price is lower
11            if (price < minPrice) {
12                minPrice = price;
13            }
14            // Calculate profit if we sell at current price
15            int profit = price - minPrice;
16            // Update maximum profit if current profit is higher
17            if (profit > maxProfit) {
18                maxProfit = profit;
19            }
20        }
21
22        return maxProfit;
23    }
24
25    // Alternative one-liner approach using Math functions
26    public int maxProfitOneLiner(int[] prices) {
27        int minPrice = Integer.MAX_VALUE;
28        int maxProfit = 0;
29
30        for (int price : prices) {
31            minPrice = Math.min(minPrice, price);
32            maxProfit = Math.max(maxProfit, price - minPrice);
33        }
34
35        return maxProfit;
36    }
37}
38
Loading visualizer...