DEV Community

Cover image for Leetcode — Top Interview 150–121. Best Time to Buy and Sell Stock
Ben Pereira
Ben Pereira

Posted on

Leetcode — Top Interview 150–121. Best Time to Buy and Sell Stock

It’s an easy problem with the description being:

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

At first you would think about sorting and getting smaller and bigger numbers, but could be that from the array you may get different ranges or numbers before and after that would cause the difference to not match what’s expected, so forget about sorting.

A good way to solve in this case is to consider the min and max and the difference while iterating the array. If the minimum is less than expected, reset everything, otherwise just keep going and update max when less than the max, and always get diff, not just the max, otherwise you may fail when we get less minimum, but not a big max number.

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i<prices.length;i++) {
            if(min > prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}
Enter fullscreen mode Exit fullscreen mode

Runtime: 2 ms, faster than 77.66% of Java online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 61.4 MB, less than 80.34% of Java online submissions for Best Time to Buy and Sell Stock.

You can still improve further removing min and using only max, but the difference is not big a deal, but nonetheless is a performance improvement.

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay