Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews.

Problem Statement

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 to sell that stock in the future.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`.

Test case#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.``````

Test case#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 <= 105 (The prices array will have 1 to 100,000 elements in the array).

Understanding the problem?

We know how stock markets are, and the question says, Buy Low, Sell High. So, we are given an input array containing integers, which are the price of stocks on a given day `i`.

At any given time, we can only purchase one stock before selling it, and only then can we consider purchasing another stock. Our goal is to maximize profits from each transaction.

"Test-Case 1 clearly explains purchasing low-priced stocks and selling them for maximum profits."

❤️
Don't forget to hit the like button and write a comment. It supports my website a lot.

Illustrations

``````Input: prices = [7,1,5,3,6,4]
Output: 5``````

When trading stocks, selling a stock on day one and buying it on day two is impossible. This goes against the basic principles of stock trading.

To maximize our profit, we can purchase the stock on the second day and sell it on the fifth day, then use the funds to purchase the stock with the highest value on the fifth day. The diagram below provides a visual representation of the maximum profit that can be obtained from the given array of stock prices.

As shown in the below figure, we are going to buy the stock on the day `2` and sell on the day `5`, which gives us the maximum profit of `6 - 1`, i.e., `5`.

Thought process

My first thoughts when looking at this problem and the questions I have are:

1. This is `prices` array, so I believe there are no negative prices?
2. What are the constraints? What if there's only a single element in the `prices` array?
3. What if the stock price on day 1 is high and on all other days is lower? Should I return `0`?

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are:

1. Brute force / Naive approach
2. Using extra auxiliary Space
3. One pass or Greedy approach

Approach 1: Naive/Brute force

Intuition

So, how will we keep track of the smallest and the largest numbers while traversing the array?

With this idea in mind, we can have two loops running, and the algorithmic steps are as follows.

Algorithm

1. Initialize a variable `maxProfit` to `0`. This variable will be used to keep track of the maximum profit.
2. The outer loop represents the day on which you consider buying the stock. Iterate through each day as a potential buying day (`buyDay`) from `0` to `prices.length - 1`.
3. The inner loop represents the day on which you consider selling the stock. For each buying day (`buyDay`), iterate through the subsequent days as potential selling days (`sellDay`) from the next day to the last day.
4. In the inner loop:
1. Calculate the current profit by subtracting the price on the buying day (`prices[buyDay]`) from the price on the selling day (`prices[sellDay]`), which can be `currentProfit = prices[sellDay] - prices[buyDay]`
2. Now, update the `maxProfit` , by doing `maxProfit = Math.max(maxProfit, currentProfit)`
5. Continue the iterations, considering different buying and selling days.
6. After completing both loops, return the final value of `maxProfit`.
``````class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
int currentProfit = prices[sellDay] - prices[buyDay];
maxProfit = Math.max(maxProfit, currentProfit);
}
}
return maxProfit;
}
}``````

Complexity Analysis

Time complexity: is `O(n^2)`.

Space complexity: Space is `O(1)`, Only variables are used here `maxProfit`, `i`, and `j`. All these three variables store `4` integer bytes and their values are updated on each iteration. So the total space occupied are `3 * 4 = 12` bytes, which is constant.

Using auxiliary space

Intuition

This approach is not recommended because we use extra space to store an auxiliary array. Can we do better than this? 🤔

Yes, a better approach uses linear search through the array. This is for your practice.

Algorithm

1. Create an auxiliary array `aux` of the same length as the prices array. Store the maximum right-side stock price at each of these indexes.
2. Initialize the last element of the `aux` array (`aux[prices.length - 1]`) with the last price in the prices array (`prices[prices.length - 1]`). Because this is the max price and there are no right elements.
3. Iterate backward through the prices array, starting from the `prices.length - 2` to `0`.
• For each index `i`, set `aux[i]` to the maximum value between the current price (`prices[i]`) and the next day's maximum price (`aux[i + 1]`).
4. Initialize a variable `profit` to `0`. This variable will be used to keep track of the maximum profit.
5. Iterate through each day in the prices array.
• For each day (`i`):
• Calculate the current profit by subtracting the current price (`prices[i]`) from the pre-calculated maximum price (`aux[i]`), using `currProfit = aux[i] - prices[i]`
• Update `profit` with the maximum of its current value and the calculated `currProfit` using `profit = Math.max(currProfit, profit)`
6. After completing the iteration, return the final value of `profit`.
``````class Solution {
public int maxProfit(int[] prices) {
int[] aux = new int[prices.length];
aux[prices.length - 1] = prices[prices.length - 1];
for (int i = aux.length - 2; i >= 0; i--) {
aux[i] = Math.max(prices[i], aux[i + 1]);
}

int profit = 0;

for (int i = 0; i < prices.length; i++) {
int currProfit = aux[i] - prices[i];
profit = Math.max(currProfit, profit);
}
return profit;
}
}``````

Complexity Analysis

Time complexity: Time is `O(N)`, where `N` is the number of elements in the prices array.

Space complexity: Space is `O(N)`, we used an auxiliary array to store the max stock on the right side of each price array element.

One pass [Greedy approach]

Intuition

We used auxiliary or extra space for the max elements to the element's right. But that takes an order `N` space, which is not at all recommended, plus a bad approach.

Here we keep track of the lowest left price and find the difference between largest price & lowest price.

We are greedy and buy the lowest stocks in a day and sell them for higher profits in the future.

Algorithm

1. Initialize `minprice` to `Integer.MAX_VALUE` and `maxprofit` to `0`. These variables will be used to keep track of the minimum price and maximum profit.
2. Iterate through each day in the prices array.
• For each day (`i`):
• If the current price (`prices[i]`) is less than `minprice`, update `minprice` to the current price.
• Else, if the difference between the current price and `minprice` is greater than `maxprofit`, update `maxprofit` with this difference.
3. After completing the iteration, return the final value of `maxprofit`.
``````class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}``````
``````// Refactoring above code for readability
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;

for (int price : prices) {
if (price < minPrice)
minPrice = price;
else
maxProfit = Math.max(maxProfit, price - minPrice);
}

return maxProfit;
}
}``````

Complexity Analysis

Time complexity: Time is `O(N)`, where `N` is the number of elements in the prices array.

Space complexity: Space is `O(1)`.

Blind75Coding Interview QuestionsArraysData Structures and Algorithms

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

Blind 75 LeetCode Problems: Detailed Solutions

💡More problems are on the way. Blind 75 is a curated collection of 75 coding problems commonly used by fast-paced startups and the top 1% of companies. List gained popularity among software engineers for tech interviews, especially at Google, Amazon, and Facebook (Meta). Arrays 1. Two Sum 2. Best Time

Members Public

Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!