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 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.
Example 2:
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^5
0 <= prices[i] <= 10^4
My Solution
The simplest way to solve this problem is to check every pair of indices and keep track of the maximum difference. However, looking at the constraints, this won’t be feasible because this would be an O(n²) algorithm. We need to find an algorithm that runs in O(n) time. One way to do this is to have two arrays called min and max. The min array keeps track of the minimum element as we scan the prices array from left to right. The max array keeps track of the maximum element as we scan the prices array from right to left. The maximum profit then, would be the maximum difference at every element of prices, by max_arr[i] - min_arr[i]. Basically at every index we are taking the maximum possible element that we could possibly take from that index and subtracting the minimum possible element from that index. This would give us the max profit.
Time complexity would O(n) because we scan the array three times to generate max_arr, min_arr, and then another time to find the max profit. Space complexity would be O(n) to maintain the min and max arrays. This is another example of making a tradeoff between space and time to reduce time complexity from O(n²) to O(n).
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[] min_arr = new int[n];
int[] max_arr = new int[n];
int profit = 0;
int min = prices[0];
int max = prices[n-1];
for (int i = 0; i < n; i++) {
min = Math.min(min, prices[i]);
min_arr[i] = min;
}
for (int i = n-1; i >= 0; i--) {
max = Math.max(max, prices[i]);
max_arr[i] = max;
}
for (int i = 0; i < n; i++) {
profit = Math.max(profit, max_arr[i] - min_arr[i]);
}
return profit;
}
}