Sliding Window - Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the i^th 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.

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.

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 <= 10⁵
0 <= prices[i] <= 10⁴

Solution 1 - Using sliding window technique, find the maximum profit window

In this approach, we are going to apply sliding window technique, using two pointers left and right find the profit between these two pointers, then adjust these pointers to find the maximum window.

Implementation steps:

First, we will create three variables left, right that we will use to adjust the window, and maxProfit to track the result. Initialize left=0 and right=1, that is the beginning window size.
Next, run a while loop until right pointer reaches end of array, and check:
- If left value is less than right value: Check the current profit using profit = prices[right] - prices[left], and update the maxProfit
- If left value is great than or equal to right value: update the left pointer to right value, since we have already checked current window and next minimum value is at right pointer.
- Always move right pointer by 1.
Finally, return maxProfit.

Example:

Consider the example with prices = [7,1,5,3,6,4].
Initially, left = 0, right =1 and maxProfit = 0.
In the first step, prices[left] is greater than prices[right], so there is no profit can be made, so update left = right = 1 and right = 2.
In the second step, prices[left] is less than prices[right], so check the profit profit = 5 -1 = 4, update the maxProfit = 4, increment right pointer right = 3.
In the third step, prices[left] is less than prices[right], so check the profit profit = 3 -1 = 2, since this profit is less than current maxProfit, we will not update it, then increment right pointer right = 4.
In the fourth step, prices[left] is less than prices[right], so check the profit profit = 6 -1 = 5, since this is higher than current maximum profit, update the maxProfit = 5, increment right pointer right = 5.
In the fifth step, prices[left] is less than prices[right], so check the profit profit = 4 -1 = 3, since this profit is less than current maxProfit, we will not update it, then increment right pointer right = 6.
Since the right pointer reached end of array, we will exit the loop, and return maxProfit found, which is 5.

public class BestTimeToBuyAndSellStock { static int maxProfit(int[] prices) { int maxProfit = 0; int left = 0; int right = 1; while(right <prices.length) { if(prices[left] < prices[right]) { int profit = prices[right] - prices[left]; maxProfit = Math.max(profit, maxProfit); } else { left = right; } right++; } return maxProfit; } public static void main(String[] args) { System.out.println(maxProfit(new int[]{7,1,5,3,6,4})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of prices array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: