Challenge #16 - Best Time to Buy and Sell Stock 
Tags: javascript, programming, codenewbie, computerscience
Published: 2021-10-04 07:18:23

Hello!

I hope you had a lovely weekend. Here is my today's journal (btw it's day 16) of [my coding diary](https://www.pankajtanwar.in/coding-diary).

<hr/>

**Problem of the day** - [Best Time to Buy and Sell Stock](https://leetcode.com/problems/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] <br/>
> **Output:** 5 <br/>
> **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.*

<hr/>

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.

```cpp
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. 

<hr/>

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** -

```cpp
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](https://twitter.com/the2ndfloorguy).

<hr/>

You might like previous editions of [my coding diary](/coding-diary)

- [Day #15 - Count Number of Pairs With Absolute Difference K.](https://www.pankajtanwar.in/code/count-number-of-pairs-with-absolute-difference-k/)
- [Day #14 - Minimum Number of Operations to Move All Balls to Each Box.](https://www.pankajtanwar.in/code/minimum-number-of-operations-to-move-all-balls-to-each-box/)
- [Day #13 - Number Of Rectangles That Can Form The Largest Square.](https://www.pankajtanwar.in/code/number-of-rectangles-that-can-form-the-largest-square/)
- [Day #12 - Unique Morse Code Words.](https://www.pankajtanwar.in/code/unique-morse-code-words/)
- [Day #11 - Count the Number of Consistent Strings.](https://www.pankajtanwar.in/code/count-the-number-of-consistent-strings/)
- [Day #10 - Find Greatest Common Divisor of Array.](https://www.pankajtanwar.in/code/find-greatest-common-divisor-of-array/)