Boats to Save People

Boats to Save People

What is this problem about?

In the Boats to Save People coding problem, you are given an array representing the weights of people and a weight limit for each boat. Each boat can carry at most two people at the same time, provided their combined weight doesn't exceed the limit. Your goal is to find the minimum number of boats required to carry everyone.

Why is this asked in interviews?

This is a popular medium-level question at companies like Microsoft, Amazon, and Google. It tests your ability to identify the correct strategy for optimization. While it might look like a dynamic programming problem at first, it's actually perfectly suited for a Greedy approach. It also evaluates your skill in using Two Pointers to traverse a sorted array efficiently.

Algorithmic pattern used

This problem uses the Greedy pattern combined with the Two Pointers interview pattern. The greedy strategy is to always try to pair the heaviest person currently available with the lightest person. If they can both fit, great; if not, the heaviest person must take a boat by themselves (as they are the most likely to exceed the limit with anyone else). By sorting the array first, you can use one pointer at the start (lightest) and one at the end (heaviest) to make these decisions in $O(N \log N)$ time.

Example explanation

Array: [1, 2, 2, 3], Limit: 3

1. Sort the array: [1, 2, 2, 3].
2. Pointers: left = 0 (val 1), right = 3 (val 3).
3. heaviest (3) + lightest (1) = 4. Over limit! heaviest (3) goes alone. (1 boat, right becomes 2).
4. heaviest (2) + lightest (1) = 3. Fits! Both go. (2 boats, right becomes 1, left becomes 1).
5. Only one person left (2). They go in a boat. (3 boats). Total boats: 3.

Common mistakes candidates make

A common mistake is trying to pair the two lightest people first, which is not optimal. Another error is forgetting the constraint that only two people can fit in a boat. Some candidates also forget to sort the array, which is a mandatory step for the two-pointer approach to work.

Interview preparation tip

Whenever you encounter an optimization problem involving "minimum number of X to cover Y," always consider if a Greedy strategy works before jumping into more complex DP. Sorting is often the key to making greedy choices obvious.