Solving Coding Problem: Best Time to Buy and Sell Stock

// Buy on day 1 and sell on day 5 for a profit of 5 - 1 = 4. 
prices = [1, 2, 3, 4, 5], return 4.
// Buy on day 4 and sell on day 9 for a profit of 11 - 1 = 10.
prices = [4, 5, 2, 1, 6, 10, 4, 9, 11], return 10.
// Buying and selling the stock at any point would yield a negative profit.
prices = [33, 18, 8, 2], return 0
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
// update our min if the current price is smaller than our current min.
min = Math.min(min, prices[i]);
}
int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
if (prices[i] > min) {
profit = prices[i] - min;
}
}
public int largestProfit(int[] prices) {
int profit = 0;
int min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
if (prices[i] > min) {
profit = Math.max(profit, prices[i] - min);
} else {
min = prices[i];
}
}
return profit;
}
# Big-O Analysis
Runtime: O(N) where N is the number of prices.
Space complexity: O(1) as we only need a few variables (regardless of the size of the prices array)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
S7rthak

S7rthak

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Codeforces(Expert)