Good day software engineers and developers! It is a Thursday morning and seems like it will be a sunny day with highs in the low 70’s F. Like I mentioned in a previous post, the days are getting shorter and cooler. My wife and I decided to walk after the workday is over. We tried it yesterday and by 06:00 PM we were back home. At that time there is daylight and the temperature is much higher than earlier in the day.
Today we will take a look at HackerRank’s Minimum Loss problem. If interested take a look at the description and give it a try.
Lauren has a chart of distinct projected prices for a house over the next several years. She must buy the house in one year and sell it in another, and she must do so at a loss. She wants to minimize her financial loss.
Seems that Lauren is attempting to buy a house and then sell it minimizing loss. I have solved a different problem on LeetCode in which we need to maximize profit when buying and selling a home. This is not the case here.
We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows computer. A more traditional appro0ach would be to solve the problem on-line using the IDE provided by HackerRank.
The signature for the function in question follows:
public static int minimumLoss(List<Long> price) {
// Write your code here
}
It seems we need to read some information, create a list, invoke the function of interest that we need to develop, and display the result.
Some time ago I solved a similar problem at LeetCode. That problem dealt with maximizing profits instead of minimizing losses. If interested in such problem I invite you to take a look at “Best Time to Buy and Sell Stock – Revisited” in this blog.
5
20 15 8 2 12
main <<< prices: [20, 15, 8, 2, 12]
minimumLoss <<< priceIndexMap: {2=3, 20=0, 8=2, 12=4, 15=1}
minimumLoss <<< prices: [2, 8, 12, 15, 20]
minimumLoss <<< dayLoss: 5
minimumLoss <<< minLoss: 5
minimumLoss <<< dayLoss: 3
minimumLoss <<< minLoss: 3
minimumLoss <<< dayLoss: 6
minimumLoss <<< minLoss: 3
main <<< minimumLoss: 3
3
5 10 3
main <<< prices: [5, 10, 3]
minimumLoss <<< priceIndexMap: {3=2, 5=0, 10=1}
minimumLoss <<< prices: [3, 5, 10]
minimumLoss <<< dayLoss: 2
minimumLoss <<< minLoss: 2
main <<< minimumLoss: 2
5
20 7 8 2 5
main <<< prices: [20, 7, 8, 2, 5]
minimumLoss <<< priceIndexMap: {2=3, 20=0, 5=4, 7=1, 8=2}
minimumLoss <<< prices: [2, 5, 7, 8, 20]
minimumLoss <<< dayLoss: 12
minimumLoss <<< minLoss: 12
minimumLoss <<< dayLoss: 2
minimumLoss <<< minLoss: 2
main <<< minimumLoss: 2
Our test scaffold is presented with two input lines. This follows the problem requirements. The first line holds the number of house prices followed by the actual prices.
Our test code ignores the first line and then reads the second one and creates a list of prices. The list is displayed to make sure all is well so far.
The answer in displayed at the end of each run. All answers seem to be correct.
The lines in between are displayed by the function of interest. They are NOT PART OF THE SOLUTION. We will refer to them while reviewing the code for the function in question.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** skip count of prices ****
br.readLine();
// **** read price list into a list ****
List<Long> prices = Stream.of(br.readLine().trim().split(" "))
.map(Long::parseLong)
.collect(Collectors.toList());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< prices: " + prices.toString());
// **** compure result and display it ****
System.out.println("main <<< minimumLoss: " + minimumLoss(prices));
}
This is our test code. We open a buffered reader, skip the first input line and then read the price values. The prices are inserted into a list. This is done to match the signature of the function we need to develop.
After calling the function of interest we display the result.
Note that we need to compute the difference between the price paid to buy the house and the price obtained when selling the house. Also note that we need to first buy a house and then sell it at the minimum loss. Is this a money laundering scheme???
/**
* Buy the house in one year and sell it in another,
* and must be done at a loss.
* One must minimize the financial loss.
* Time: O (n log(n)) - Space: O(n)
*/
public static int minimumLoss(List<Long> prices) {
// **** sanity check(s) ****
if (prices.size() < 2) return 0;
// **** initialization ****
long minLoss = Long.MAX_VALUE;
long dayLoss = 0;
// **** allocate and populate map for prices and indices - O(n) ****
Map<Long, Integer> priceIndexMap = new HashMap<>();
for (int i = 0; i < prices.size(); i++)
priceIndexMap.put(prices.get(i), i);
// ???? ????
System.out.println("minimumLoss <<< priceIndexMap: " + priceIndexMap.toString());
// **** sort the price list - O(n log(n)) ****
Collections.sort(prices);
// ???? ????
System.out.println("minimumLoss <<< prices: " + prices.toString());
// **** traverse the sorted list of prices from
// high to low looking for the minimum loss - O(n) ****
for (int i = prices.size() - 1; i > 0; i--) {
// **** skip indices out of order (need to BUY before SELL) ****
if (priceIndexMap.get(prices.get(i)) > priceIndexMap.get(prices.get(i - 1)))
continue;
// **** compute day loss ****
dayLoss = prices.get(i) - prices.get(i - 1);
// ???? ????
System.out.println("minimumLoss <<< dayLoss: " + dayLoss);
// **** update the minimum loss ****
minLoss = (dayLoss < minLoss) ? dayLoss : minLoss;
// ???? ????
System.out.println("minimumLoss <<< minLoss: " + minLoss);
}
// **** return the minimum loss ****
return (int)minLoss;
}
I always like to start by performing some sanity checks. In this case if we have no prices or a single one, the profit is 0. In order to proceed we need at least two prices. The first will be the buying price and the second the selling price.
Skip down to the next code snippet to take a look at alternate code for the sanity checks section. I will wait for you to return after looking at the alternate sanity check section… …Welcome back!
We initialize two variables. The first keeps track of the minimum loss and the second of the loss per day (or was it per year?). I went back to the requirements and each price represents a year, not a day. That said; both are equivalent. What we need to consider is that we must first purchase the house and then we need to sell it on a different future year (not day; sorry about that).
The idea is to sort the prices in an ascending order so we can compare adjacent prices and determine if they are `valid` or not (more on this shortly). If they are valid, then we are free to compute the loss and then check if it is smaller than the current loss. If so we update the running loss.
What does `valid` means in the context of this problem? By sorting the prices in ascending order, we can easily compute the loss but we need to determine if the prices we are comparing were generated in the proper order. Remember that we first need to buy the property and then sell it. We cannot sell something we have not bought yet.
The map is used to remember the positions of each unique price per year.
We then sort the value which will change the positions in the list of prices.
We will traverse the sorted list from end to start. This will allow us to minimize the loss as we progress in the loop. Of course the opposite sorting order would have allowed us to traverse the list from first to last with a slightly different code.
First we check that the two consecutive prices were in the proper order in the unsorted list. If not; we skip this entry.
We then compute the loss.
Once we have the loss we check if it is smaller than the running loss in the `minLoss` variable. If so we update it.
When all is said and done, we return the integer value for the minimum loss as required.
// **** sanity check(s) ****
if (prices.size() < 2) return 0;
if (prices.size() == 2) {
if (prices.get(0) < prices.get(1)) return -1;
else return (int)(prices.get(0) - prices.get(1));
}
The first line is the same code as we have in the function of interest.
The second test if for cases in which we have two prices. Since the prices are unique, we only have two possibilities. The first price is lower than the second. This is not acceptable because Lauren would make a profit, so we return a -1. In the second case the second price is larger than the first, so we incur in a loss. Since there are no more prices, we return the price difference.
As I was writing this blog, I thought that thinking about the case of two prices will help better understand the code for the function of interest.
If you are on your first read of the post, please go back to the code for the function of interest; otherwise just keep on reading.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository. Note that I did made some changes to the copy of the code in the repository by adding the second sanity check and changing the name of the `dayLoss` variable to `yearLoss`.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John