Challenge #16 - Best Time to Buy and Sell Stock

Hello!

I hope you had a lovely weekend. Here is my today's journal (btw it's day 16) of my coding diary.

---

Problem of the day - Best Time to Buy and Sell Stock

Tag - Easy

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.

---

Ahh, quite a famous problem. It's the most favorite interview challenge of every interviewer for an entry-level job. Let's try and see if I am a good fit for an entry level job🤭.

So, the problem is pretty straightforward. I just need to find the maximum possible difference between two numbers (in increasing order only).

Well, I welcome my dearest friend, brute force approach. Directly coded the solution within seconds.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i=0;i<prices.size();i++) {
            for(int j=i+1;j<prices.size();j++) {
                ans = max(ans, prices[j]-prices[i]);
            }
        }
        return ans;
    }
};

Hit submit and ....... Leetcode shattered all my hopes, with a beautiful Time Limit Exceeded message.

Well, I need to find some optimized way, brute force doesn't work always.

---

So, I need to find the maximum difference between a number with all numbers next to him. For that, I just need to know what is the maximum number among all those numbers.

Oh man, pretty easy peasy. I will iterate from backward and keep on tracking the maximum number till date and with each number, I will calculate the difference and see if it's the maximum or not.

Don't worry, here is the code -

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int max_val = INT_MIN;
        for(int i=prices.size()-1;i>=0;i--) {
            max_val = max(max_val, prices[i]);
            ans = max(ans, max_val - prices[i]);
        }
        return ans;
    }
};

Woohoo, all ticks green. No pain full TLE this time. Ummm, it was a nice problem. Interesting thing was, test cases were designed so beautiful that one can't celebrate his brute approach submission.

As always, if you have any thoughts about anything shared above, don't hesitate to reach out to me.

---

You might like previous editions of my coding diary

• Day #15 - Count Number of Pairs With Absolute Difference K.
• Day #14 - Minimum Number of Operations to Move All Balls to Each Box.
• Day #13 - Number Of Rectangles That Can Form The Largest Square.
• Day #12 - Unique Morse Code Words.
• Day #11 - Count the Number of Consistent Strings.
• Day #10 - Find Greatest Common Divisor of Array.