Best Time to Buy and Sell Stock — Popular Coding Interview Question

In this post, we will go through this popular interview question, starting from a brute-force solution and gradually optimizing it to an elegant approach.

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.

Brute Force Approach

The most straightforward approach is to calculate the profit for every pair of days and return the maximum profit. We can achieve this using two nested loops.

Here’s a simple implementation in Java:

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            int profit = prices[j] - prices[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }…