Leetcode 123. Best Time to Buy and Sell Stock III [ Algorithm + Code Explained]

One of the most frequently asked coding interview questions on Array in companies like Google, Facebook, Amazon, LinkedIn, Fintech firm like Morgan Stanley, Goldman, J P Morgan, Microsoft, Uber, Apple, Adobe etc.

LeetCode : Best Time to Buy and Sell Stock III


Question :Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

[hussainmusthaq]

To people who might still have questions against this good explanation. You have two transactions, you are trying to minimize first buy with lowest out of pocket and maximize remaining amount after second purchase against profit1. The key to this problem is the sliding window concept in first buy.

[rajathw]

It takes an extra effort to understand how this technique works but once you do, you see how clever it is

[tanmayrauth]

How to come up with such amazing solution during interview is an important question

[roshanmhatre]

Your videos are really good ma'am. Could you make videos on the Interviews of FB and how you prepared for them especially for FB

[mritunjaychoubey]

wooow, this was good. Nice work, This is your first video that I saw, great content and very straightforward explanation.

[prakulcool]

This wasn't a very clear explanantion!

[abrarjahin]

The algorithm is not explained properly, not clear

[mrdude]

Make videos on Tallest billboard and Skyline problem please. Appreciate your work.

[AbhijeetNayak-connect]

@jayati Can you come up with this algorithm in a real interview if you haven't read the leetcode most voted solution?

[kashishgupta]

A very clear explanation maam, thank you !

[shristygupta]

Everywhere they have used atleast 20-25 lines used dp etc and you have done in almost 15 lines wow!

[arihantjain]

Well great explanation!! But I think this is a greedy algorithm and a bottom up approach. Can you provide a recursive top down approach i.e. DP with memoization.

[aditya]

I wished someone made a generalised solution for all the models!

[Impromptu]

Is it like ur bying and selling on same day

[rahulbhati]

Can you tell me it's dp recursive solution

[nandinibagga]

i think i am in love with you and your solution.

[devadityasati]

u r amazing .. i like you, ur way of explaining and everything.

[code]

Hi can you please add word break problem leetcode

[theja]

The fact that you don't follow a step by step manner from naive to optimal shows your incompetence (at least in teaching).

[shubhamkumar-hxfb]

this method is not intuitive...dp solution is more intuitive and then convert that solution to sapce optimization