Ace Your Next Coding Interview: Solving the “Best Time to Buy and Sell Stock” Question

Hello everyone, I am a software developer with 7 years of experience in backend development. Throughout my career, I have had the opportunity to work at some of the top product-based companies in the world. In this blog post, I am excited to share my insights on one of the most common interview questions for software developers, the Best Time to Buy and Sell Stock problem.

This is a post in my series “Ace Your Next Coding Interview” posts where I am discussing popular DSA (Data Structures and Algorithm) interview questions. I will be providing various approaches to solving these problems and providing code examples in Java. Whether you are a beginner or an experienced developer, I hope you find this information useful in your journey to becoming a better programmer and ace your next DSA interview.

Problem

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.

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 <= 105
• 0 <= prices[i] <= 104

Brute force approach

The brute force approach to solve this problem is to check all possible combinations of buying and selling stocks and return the maximum profit.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            // i is the buying day
            for (int j = i+1; j < prices.length; j++) {
                // j is the selling day
                //updating maxProfit by taking maximum of current maxProfit or difference between selling price and buying price
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}

Optimized approach

A better approach to solve this problem is to keep track of the minimum stock price and calculate the maximum profit every time we encounter a new stock price.

class Solution {
    public int maxProfit(int[] prices) {
        //initializing minimum stock price as maximum value possible for int
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            //updating minimum stock price
            minPrice = Math.min(minPrice, prices[i]);
            //updating maxProfit by taking maximum of current maxProfit or difference between current stock price and minimum stock price
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}

This approach has a time complexity of O(n) as we are traversing the prices array only once.

Common mistakes

• Not keeping track of the minimum stock price.
• Not updating the maximum profit every time we encounter a new stock price.
• Not handling edge cases like empty prices array or prices array of length 1.

Conclusion

The Best Time to Buy and Sell Stock problem is a common interview question that can be solved using a brute force approach with a time complexity of O(n²) or using an optimized approach with a time complexity of O(n). It is important to keep track of the minimum stock price and update the maximum profit every time we encounter a new stock price.

I hope you found this post informative and useful. Stay tuned for more DSA interview question blog posts in the series. Follow me for more updates and insights on popular DSA interview questions or engineering mentorship.

To learn more about Ace Your Next Coding Interview series, checkout https://sde-mentor.medium.com/list/ace-your-next-coding-interview-series-a847a9d1e57f

To learn more about mentorship, Checkout my mentorship series here: https://medium.com/@sde-mentor/list/mentorship-series-be62191a4c87