Best Time to Buy And Sell Stock LeetCode

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

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.

 NOTE:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

------------------------------------------------------------------

This problem is popular in LeetCode A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

SOLUTION:

This problem is very common and also often termed as the maximum contiguous sub-array problem. The twist with this problem is that we are interested in difference of the price on buying day and the price on the selling day, rather than the sum of the days in the range. 

IMPORTANT

To handle the twist, we first create an array of length prices.length -1 to store the difference of the prices on the consecutive days.

We could have used the brute force approach to get O(n^2) solution as well, but here we use the divide and conquer method to solve the problem, which in fact is very interesting.

We divide the price diff array into three parts - the left, the right and the whole (continuous) and find the maximum value on those sub-arrays. The process goes on recursively, till we are left with an array with single element. This solution is relatively better and has complexity of O(N*logN).

The code is self-explanatory and comes with some test cases as well.

Source code: Java (GitHub)

Solution