A week of LeetCode (day 3/7)
Welcome to the third episode of our technical interview preparation series. My goal is to pave the way for you to land your dream job with ease by providing you with real problem-solving skills covering lots of topics.
Ready? Let’s jump right in!
Day 3: Boats to Save People
I will assume you haven’t read the task description, so here is a summary:
Given an array w, where w[i] is the weight of the ith person, you have an infinite amount of boats, each boat has a capacity of L, and can carry up to two persons.
what is the minimum number of boats you need to carry all people?
A good way of approaching this problem is by breaking it into smaller sub-problems. Let’s do so!
Look at the following slightly simpler problem:
Let say you have assigned some person to the first boat and there is still some remaining space R. What is the best choice you can make about that extra space.
Hint: imagine you only have two unassigned people (of different weight) that can fit in that extra space. Which one should you choose?
Obviously, if we need to accommodate only one person and we have a space R, then it is always better to choose the largest one that can fit. The easiest way to reason about it is:
By choosing the largest person who can fit into R, you are wasting less space than accommodating a person with less weight.
More rigorously, if you don’t choose the largest person who can fit (let’s call him X) and choose another one with a smaller weight (let’s call him Y), then you can find a solution that is at least as good by swapping the places of X and Y.
Now back to our original problem: We now have a strategy for choosing the second person on each boat, but how do we choose the first one?!
It turns out to be a slightly harder decision to do, but we can still apply the same logic but we still need simple observation.
The simple observation: the order we assign people to boats doesn’t matter, and at the end everyone is going to be on some boat.
You may think that is too obvious and that observation doesn’t help us much, but let’s dig into that direction and mine more valuable observations.
1- each person will be assigned to a boat.
2- that means the heaviest person is assigned to some boat.
3- somehow the heaviest person is the most demanding one and doesn’t give us too many choices, so it makes sense to start by assigning him.
This logic of thinking is referred to as greedy thinking which says, if you have to decide, then choose the option that seems most convenient at the moment without worrying about future decisions, I know it might not be the best life lesson but it is useful in solving algorithmic tasks ;)
Remember how we started by choosing the heaviest person, and when we have a boat with one person, we assign the other one by choosing the heaviest one that can fit, we are kinda thinking about the best thing to do about that one boat without thinking about other future boats we might need.
Let’s elaborate with some pseudo-code:
answer = 0
sort the people by weightsrepeat until all people are assigned to boats :-
1-pick the heaviest person and assign it to some boat.
2-calculate the remaining space R on that boat.
3-if there is some people with weight <= R who are not assigned.
4-then pick the heaviest one of them and assign it to that boat.
We have found a strategy for the task, let's write some code!
My C++ implementation:
How we approached today’s task, and how to approach other challenges?
- Break the problem in your hand into smaller sub-problems: this technique is very useful, as smaller problems tend to have simpler and sometimes well-known solutions.
- Think about how to solve the smaller sub-problems efficiently and combine them into one final happy solution.
- Change the setting of the problem and make assumptions that help you better interpret the problem in front of you: notice that we sorted the original array in order to run our greedy algorithm.
- Reread this article many times until you fully appreciate it, especially if it is your first time to see a greedy approach in action.
Your Turn:
Congratulations! If you made it here in one sitting, I knew you could do it.
Now that you hopefully acquired some new skills, Don’t stop here, put them into practice.
Go play with the code and write it by yourself from scratch, and challenge yourself to come up with examples of problems that could be solved using a greedy approach.
Additional Problems for practice:
