It is Sunday morning on a gloomy and cold day in fall in the Twin Cities of Minneapolis and St. Paul.
Last evening my wife and I watched Peppermint on Netflix. We both like most of the movies with Jennifer Garner. The ending of the movie could be somewhat debatable. In a nutshell, the husband and daughter in the movie are murdered by a drug dealer. They did not happen to be a casualty, they were all targeted. The core of the movie is based on what the surviving mother does to get justice for what happened. Towards the end of the movie she completes her tasks. Then the part that might be debatable is shown. I am not going to spoil the ending in case you are interested in watching the film. My wife and I liked what transpired in the last couple minutes of the movie.
Most Sunday’s my wife and I go to Trader Joe’s for groceries. Yesterday we checked and decided to skip. The only item that we would like to get in the next week or so is a turkey. With the leftovers from Thanksgiving we made some Ciabatta bread sandwiches with mayonnaise, lettuce, tomatoes, avocados, turkey and some truffle sauce which we liked so much that we would like to repeat the experience for the upcoming holidays.
I selected LeetCode 121 Best Time to Buy and Sell Stock. It is ranked as an Easy problem by LeetCode, but it made me think a long time in the best way to solve it. I thought you might like it.
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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
So we are given an array on integers with the price of a stock for a set of days. We are supposed to buy and then sell the stock maximizing profits (no brainer there). We should only perform a transaction per day. The obvious is then stated that we are not allowed sell stock before we purchase it.
The requirements are very well defined. Let’s take a look at the two examples provided.
7,1,5,3,6,4 main <<< prices: [7, 1, 5, 3, 6, 4] <<< i: 0 minPrice: 7 maxProfit: 0 <<< i: 1 minPrice: 1 maxProfit: 0 <<< i: 2 minPrice: 1 maxProfit: 4 <<< i: 3 minPrice: 1 maxProfit: 4 <<< i: 4 minPrice: 1 maxProfit: 5 <<< i: 5 minPrice: 1 maxProfit: 5 main <<< profit: 5 7,6,4,3,1 main <<< prices: [7, 6, 4, 3, 1] <<< i: 0 minPrice: 7 maxProfit: 0 <<< i: 1 minPrice: 6 maxProfit: 0 <<< i: 2 minPrice: 4 maxProfit: 0 <<< i: 3 minPrice: 3 maxProfit: 0 <<< i: 4 minPrice: 1 maxProfit: 0 main <<< profit: 0
Let’s first concentrate on the values for the input line. We need to buy low and sell high. The problem is when to buy low and when to sell high. It seems that if we buy on day 1 the stock priced at 1 and then sell it on day 4 at 6, we should be able to get 6 – 1 = 5 units of currency (in whatever that might be).
Now let’s turn our attention to the input of the second example. It seems that no matter in which day we purchase stock, we will not be able to sell it and make a profit.
The problem is catalogued by LeetCode under arrays and dynamic programming. In the Wikipedia page of Dynamic Programming take a look at the section labeled Computer programming. It provides the two key attributes (optimal substructure and overlapping subproblems) that a problem must have in order to be able to be solved using this technique.
I decided to solve the problem in my Windows 10 home computer, using Java, and the VSCode IDE.
public int maxProfit(int[] prices) {
}
The function / model signature indicates that we need to pass to it an array of integers. The rest is done by the function that we need to develop.
Our test scaffolding (which IS NOT PART OF THE SOLUTION) should read the input line, create an array and populate it with the integer representations found in the input string.
Please disregard the messages that follow until the result is returned and printed.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read price data ****
String[] strs = br.readLine().trim().split(",");
// **** close buffered reader ****
br.close();
// **** create and populate array of prices ****
int[] prices = Arrays.stream(strs)
.mapToInt(Integer::parseInt)
.toArray();
// ???? ????
System.out.println("main <<< prices: " + Arrays.toString(prices));
// **** compute and display the day to sell ****
System.out.println("main <<< profit: " + maxProfit(prices));
As expected, we open a buffered reader, read the input line and close the buffered reader. This time I decided to use a stream to convert the values into integers and return them in an integer array. The resulting array is then displayed. The values appear to match so we are ready to start solving the problem. The results will be displayed when the function completes.
/**
* Track min price (when to buy).
* Track max profit (when to sell).
* O(n)
*/
static int maxProfit(int[] prices) {
// **** sanity check(s) ****
if (prices.length == 0)
return 0;
// **** initialization ****
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;
// **** traverse the array of prices ****
for (int i = 0; i < prices.length; i++) {
// **** look for the min stock price (when to buy) ****
if (prices[i] < minPrice) {
minPrice = prices[i];
}
// **** compute max profit (when to sell) ****
else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
// ???? ????
// System.out.println( "<<< i: " + i + " minPrice: " + minPrice +
// " maxProfit: " + maxProfit);
}
// **** return profit ****
return maxProfit;
}
We start by performing a sanity check. As you can see not much is saved in this case. We then initialize two variables. We will keep track of the maximum profit we would make on each day if we had purchased the stock earlier in the specified time span. The other variable keeps track of the minimum price for the stock as days go by.
The loop traverses the time span. Each day we check if the price is lower than it was before. We then update the minimum price, but we do not compute the profit made if we sell because we are not allowed to sell on the same day we purchase.
If we do not purchase because the price is low, then the price could be higher, so we could sell. We do not sell but keep track of the profit if we would have sold.
Spend time making sure the logic makes sense. As you can see, for each loop we display the day i, the minimum price and the profit we could make if we would sell. Note that the maximum price may happen before we complete the traversal of the time stamp. Check the profits in the first example. The first two days do not count. Then the profit starts increasing but it remains at two levels for four days.
The main difficulty for me was that in real life on day 4 when the price is at 6 we NEED to sell, otherwise on day 5 the price goes down to 4 and it is too late to sell and maximize profits. Nice as an exercise but do not go out and invest using this approach because it is of no value in the stock market.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,841 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com