Prepare for your coding interviews one byte at a time.

Work through a single problem each day, delivered to your inbox, in an order that encourages learning as opposed to rote memorization.

Curated curriculum tailored to honing your skills

Learn all the most popular interview topics one concept at a time in an order that makes sense. Start with easier topics and progress to harder topics to ensure you build a solid foundation as you practice. Cover our organized, twelve week curriculum before receiving randomly selected questions and learn how to solve the most frequently asked questions from the most popular companies.

Strings
Hash Maps
Linked Lists
Weeks 1-3
Stacks & Queues
Trees
Breadth-first Search
Depth-first Search
Weeks 4-7
Backtracking
Greedy Algorithms
Memoization
Dynamic Programming
Advanced Topics
Weeks 8-12

Carefully crafted questions and solutions

See a sample of the emails you will receive below. Everything is exactly how it will look in your inbox. Normally the link near the top will be a link to the solution for the prior day; however, in this case you can click the link to see the solution to the current problem.

Solution

You've probably heard of the expression "buy low, sell high" and that's exactly how we're trying to solve our problem today. Our goal is to find the optimal point to buy (lowest point) and optimal point to sell (highest point after we've bought). By finding these two points we can then calculate our profit as follows price we sold at - price we bought at. Let's first focus on finding the low price. This is as easy as using a for loop and updating a min variable any time the current price is lower than our min.

                        
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    // update our min if the current price is smaller than our current min.
    min = Math.min(min, prices[i]);
}
                        
                    

Now that we understand the logic that we can use to find the low price and therefore the price at which we should buy our stock, now we just need to understand when to sell our stock. This can be accomplished by simply checking if our current stock price is greater than our min, if it is let's simulate selling at that point.

                        
int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    if (prices[i] > min) {
        profit = prices[i] - min;
    }
}
                        
                    

Great now we're recording our profit! However, because we are always reassigning our profit to the current calculation if the current price is greater than our min, we are not guaranteeing that we always store the largest profit. Now, using our two methods of finding the low price and simulating making transactions, with some slight tweaking, we can guarantee that we always store the max profit!

                        
public int largestProfit(int[] prices) {
    int profit = 0;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < prices.length; i++) {
        if (prices[i] > min) {
            profit = Math.max(profit, prices[i] - min);
        } else {
            min = prices[i];
        }
    }

    return profit;
}
                        
                    

This problem seems complicated, but really just boils down to the code above. Our solution correctly updates a minimum value as necessary while simultaneously simulating making trades for any prices that is greater than our minimum at the time. Now with our changes we are guaranteeing that we only reassign our profit if it yields a larger value!

                        
# Big-O Analysis
Runtime: O(N) where N is the number of prices.
Space complexity: O(1) as we only need a few variables (regardless of the size of the prices array)