The Cholocalate Milk Rule: Knowing when to sort your input [Technique Tuesdays]
AKA as the chocolate milk rule.
Hello all,
I’m sure you’ve seen it as you search it online. For certain questions, the solutions involve sorting the input. All the solution gurus will tell you to take that step. However, nobody actually tells you how they figured out that sorting would lead to the solution. It’s not their fault. In most cases, the guru themself doesn’t know. They just did 500 Leetcode problems, and pattern matched their way through it. Or they spent hours on the problem, trying everything they could till they came up with the solution. But let’s be honest nobody has the time for this. And you don’t want to memorize the solutions. So what should you do?
Today, we’ll be going over a simple system that will help you identify when sorting your input will be helpful in coming up with the final solution. OG readers will know that I covered this on one of the solutions prior. We called it the chocolate milk rule at that stage. You can see it here: [Solution]Problem 35: 3 Sum[Netflix]. This is a more general version of what we discussed there.
Key Takeaways
The important ideas discussed today are-
What is the chocolate milk rule- In cases where our solutions follow certain ordering properties and we want to filter out candidate solutions based on that ordering, we want to sort our input.
What properties does CMR need- As long as we know that the solutions can be reasonably ordered by going higher or lower and that the solutions are generated from a combination/subset of the input, CMR might be a good candidate.
CMR in different contexts- 3 Sum, 2 Sum Sorted, and even Search. We will look at all of these and see how our rule applies.
Why CMR works- When we care about the magnitude of the solutions (as a filter) sorting it allows us to add an ordering to our candidate solutions. This makes sorting much easier.
Sound exciting? Let’s get into it.
How to Know when to sort the array
When it comes to Leetcode, sorting the input is always one of those steps that come out of nowhere. When I was starting off, nobody could tell me what made them think of sorting as they were coming up with the solution. So I put some effort into it and noticed the following similarities in all solutions where sorting was needed.
Firstly, I noticed that all the questions ultimately filtered candidate solutions by magnitude. For the aforementioned 3Sum, we cared whether our combination sum was greater than or lesser than (or matched) 0. This checks out for 2 Sum and variants of nSum. But what about searching? There’s no sum there.
Well, the magnitude we filter by is different. In the case of Binary Search, this magnitude is the ordering of our strings. We know whether a string is greater than or lesser than a given string, according to the rules of our alphabet. And that comparison is exactly what we use to filter out our solutions.
The second bit is more obvious, but it’s always good to make such things clear. I have found that stating the obvious helps you recall and make things more explicit. This allows you to catch yourself from making silly mistakes. So what is this second bit? Simply put, we will sort the array when our candidate solutions will be created by taking subsets from the input.
Why CMR works
I’ve given you the details about CMR. And hopefully, none of it is too shocking. But it might not be obvious why this will work. Let me break it down. By the end, you will understand why.
Think about the magnitudes of candidate solutions. We know that replacing a member of the smaller solution with a smaller value will definitely reduce the overall magnitude. The opposite case for substituting in bigger values.
This can get a little abstract so let’s go back to 3Sum. Substituting a smaller number in our sum will reduce the sum. Replacing one value with a bigger value will increase the sum. What does this have to with sorting?
Sorting will implicitly allow you to take advantage of this idea. In a sorted list, we know how going left or right in the list will change the values we can use. This should make the reason for sorting clearer. A sorted input would make filtering by magnitude easier.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75