Best Time to Buy and Sell Stock in Java

Solving the Best Time to Buy and Sell Stock Problem in Java When it comes to algorithmic problem-solving, one of the classic challenges that developers encounter is the "Best Time to Buy and Sell Stock" problem. This problem is a great exercise in optimizing for maximum profit while adhering to specific constraints. In this blog post, we'll dive into an elegant and efficient solution written in Java, explore how it works, and break down its logic step by step. Problem Statement The problem is straightforward yet intriguing: You're given an array prices, where prices[i] represents the price of a stock on the ith day. Your goal is to maximize your profit by choosing a single day to buy the stock and a different day in the future to sell it. The catch? You can only make one transaction (i.e., one buy followed by one sell), and if no profit can be made, you return 0. Here are the key details: Input: An array of integers prices representing daily stock prices. Output: The maximum profit achievable, or 0 if no profit is possible. Constraints: 1

Mar 12, 2025 - 08:25

Solving the Best Time to Buy and Sell Stock Problem in Java

When it comes to algorithmic problem-solving, one of the classic challenges that developers encounter is the "Best Time to Buy and Sell Stock" problem. This problem is a great exercise in optimizing for maximum profit while adhering to specific constraints. In this blog post, we'll dive into an elegant and efficient solution written in Java, explore how it works, and break down its logic step by step.

Problem Statement

The problem is straightforward yet intriguing: You're given an array prices, where prices[i] represents the price of a stock on the ith day. Your goal is to maximize your profit by choosing a single day to buy the stock and a different day in the future to sell it. The catch? You can only make one transaction (i.e., one buy followed by one sell), and if no profit can be made, you return 0.

Here are the key details:

Input: An array of integers prices representing daily stock prices.
Output: The maximum profit achievable, or 0 if no profit is possible.
Constraints:
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4

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: Prices only decrease, so no profit can be made.

The Solution

Here’s the Java code that solves this problem efficiently:

import static java.lang.Math.*;

class Solution {
    public int maxProfit(int[] prices) {        
        int profit = 0;
        int buy = 10_001; // A value larger than the max possible price
        for (int i = 0; i < prices.length; i++) {
            profit = max(prices[i] - buy, profit);
            buy = min(prices[i], buy);
        }
        return profit;
    }
}

This solution is concise, runs in O(n) time (where n is the length of the prices array), and uses O(1) extra space. Let’s break it down.

How It Works

Key Insight

The problem asks for the maximum profit from a single buy-sell transaction. This means we need to find the maximum difference between two elements in the array, where the smaller element (buy price) comes before the larger element (sell price). Rather than checking every possible pair of buy and sell days (which would take O(n²) time), we can optimize this by tracking the minimum price seen so far and calculating the potential profit at each step.

Step-by-Step Explanation

Initialize Variables:
- profit: Starts at 0, representing the maximum profit found so far.
- buy: Initialized to 10_001, a value greater than the maximum possible price (10^4). This ensures that the first price in the array will update it.
Iterate Through the Array:
- For each day i, we:
  - Calculate the potential profit if we sell at prices[i] after buying at the lowest price seen so far (buy). This is done with max(prices[i] - buy, profit).
  - Update buy to be the minimum of the current price prices[i] and the previous buy value, ensuring we always have the lowest price encountered up to this point.
Return the Result:
- After the loop, profit holds the maximum achievable profit.

Example Walkthrough

Let’s run through the first example: prices = [7, 1, 5, 3, 6, 4].

Day (i)	Price	Buy (before)	Profit (before)	New Profit	New Buy
0	7	10,001	0	max(7 - 10,001, 0) = 0	min(7, 10,001) = 7
1	1	7	0	max(1 - 7, 0) = 0	min(1, 7) = 1
2	5	1	0	max(5 - 1, 0) = 4	min(5, 1) = 1
3	3	1	4	max(3 - 1, 4) = 4	min(3, 1) = 1
4	6	1	4	max(6 - 1, 4) = 5	min(6, 1) = 1
5	4	1	5	max(4 - 1, 5) = 5	min(4, 1) = 1

After the loop, profit = 5, which matches the expected output.

Why It Works

Correctness: The algorithm ensures that for every sell price, we’re subtracting the smallest buy price seen before it, satisfying the "buy before sell" rule.
Efficiency: It only requires a single pass through the array (O(n) time) and uses two variables (O(1) space).
Edge Cases: It handles cases where no profit is possible (e.g., decreasing prices) by keeping profit at 0 when negative differences occur.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the prices array. We only traverse the array once.
Space Complexity: O(1), as we only use two variables (profit and buy) regardless of input size.

Conclusion

The "Best Time to Buy and Sell Stock" problem is a fantastic example of how a seemingly complex task can be distilled into a simple, efficient algorithm with the right approach. By tracking the minimum price and updating the maximum profit in one pass, this solution avoids unnecessary comparisons and delivers optimal performance.

Whether you’re preparing for coding interviews or just sharpening your problem-solving skills, this problem and its solution are worth adding to your toolkit. Try it out with different test cases, and see how elegantly it handles the constraints!

Happy coding!