← Back to Index

📚 Boats to Save People – Java Cheat Sheet

📌 What Is It?

The Boats to Save People problem involves determining the minimum number of boats required to save people, given that each boat can carry at most two people and has a weight limit.

🧱 Pattern Template

Two-Pointer Greedy Algorithm

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people); // Sort people by weight
        int left = 0, right = people.length - 1;
        int boats = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++; // Pair the lightest and heaviest person
            }
            right--; // Always use a boat for the heaviest person
            boats++;
        }

        return boats;
    }
}

▶️ View Animation

📊 Time Complexity

• Sorting: O(N log N), where N is the number of people.
• Two-Pointer Traversal: O(N), for iterating through the array.
• Total Complexity: O(N log N).

✅ Use Cases

• Minimizing resources (boats) to transport people or items.
• Solving problems involving pairing elements with constraints.

📘 Common LeetCode Problems

• 881. Boats to Save People [Medium] Greedy

🧪 Example

Input: people = [3, 2, 2, 1], limit = 3
Output: 3

Explanation:
- Boat 1: [1, 2]
- Boat 2: [2]
- Boat 3: [3]

💡 Pro Tips

• Sort the array to efficiently pair the lightest and heaviest person.
• Use two pointers: one starting from the lightest person and the other from the heaviest.
• Always decrement the pointer for the heaviest person, as they must use a boat.