Welcome to this tutorial, where I aim to demystify one of the most intriguing and commonly encountered problems in software engineering interviews: the "Max Stock Profit" challenge from LeetCode (LeetCode 121).

This problem is not just a test of your coding skills, but also your ability to think analytically and optimize solutions. Whether you're an experienced engineer brushing up on your interview skills or new to the realm but confident in your coding prowess, this post is crafted to guide you through solving this problem efficiently.

Introduction to the Problem

Imagine you're given an array where each element represents the price of a stock on a given day. Your task is to choose the best day to buy and the best day to sell to maximize your profit. There's a catch, though: you cannot sell the stock before you buy it.

For example, given prices = [7,1,5,3,6,4], the optimal solution would be to buy on day 2 (price = 1) and sell on day 5 (price = 6), netting a profit of 5. Conversely, for prices = [7,6,4,3,1], no profit can be made, so the return should be 0.

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

Understanding the Solution

The key to solving this problem lies in identifying the lowest buying price and the highest potential selling price following that day. This involves iterating through the list of prices while keeping track of two variables: the minimum price found so far and the maximum profit that can be achieved.

This approach ensures we have a time complexity of O(n), as the array is traversed only once. Space complexity is kept at O(1), since only a few variables are used, regardless of the input size.

Solution in Python

def maxProfit(prices):
    # Initialize variables to track minimum price and maximum profit
    max_price, min_price = 0, float('inf')
    for price in prices:
            # Update minPrice if a new minimum is found
            min_price = min(min_price, price)
            price = price - min_price
            # Update maxProfit if the current price - minPrice is greater than the current maxProfit
            max_price = max(max_price, price)
    return maxProfit

# Example usage
prices1 = [7,1,5,3,6,4]
print(maxProfit(prices1))  # Output: 5

Solution in TypeScript

function maxProfit(prices: number[]): number {
    let minPrice: number = Infinity;
    let maxProfit: number = 0;

    for (let price of prices) {
        if (price < minPrice) {
            // Update the minimum price found so far
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            // Calculate and update max profit if current profit is greater
            maxProfit = price - minPrice;
        }
    }

    return maxProfit;
}

// Sample usage
const prices1 = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices1)); // Expected output: 5

Solution in Java

public class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                // Update minPrice with the lowest price found
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                // Update maxProfit if selling now is more profitable
                maxProfit = price - minPrice;
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] prices1 = {7, 1, 5, 3, 6, 4};
        System.out.println(solution.maxProfit(prices1)); // Output: 5
    }
}

Conclusion

The "Max Stock Profit" problem is a fantastic opportunity to showcase your problem-solving skills and your proficiency with optimizing algorithms. By understanding the logic behind the solution and learning how to implement it in different programming languages, you're not just preparing for interviews; you're also honing skills that are crucial for real-world software development.

Remember, the journey of mastering coding challenges is continuous, and every problem solved is a step forward in your career. Happy coding, and best of luck with your interviews!