---

1. Problem Summary

You are given:

• an integer array people, where each value represents a person’s weight
• an integer limit, representing the maximum weight a boat can carry

Rules:

• Each boat can carry at most two people
• Total weight on a boat must be ≤ limit
• You may not exceed the limit
• Each person must be rescued exactly once

Your task is to compute the minimum number of boats required to rescue everyone.

Example interpretation:
If:

people = [3,2,2,1]
limit = 3

Possible grouping:

(1,2), (2), (3)

Total boats:

3

---

2. Key Insights

1. Greedy pairing strategy works

To minimize boats, we should try pairing the lightest with the heaviest person.

2. Sorting enables two-pointer optimization

After sorting:

• heaviest person tries to share with lightest person
• if weight fits: pair them
• if not: send heaviest alone

3. Only two people max per boat

This simplifies choices drastically.

4. Every decision finalizes one boat

Each iteration consumes at least one person.

5. This greedy strategy is proven optimal

Pairing largest with largest wastes rescue capacity.

---

3. Approach

Two-pointer Greedy after sorting

Steps:

1. Sort array people
2. Initialize: left = 0 // lightest right = people.length - 1 // heaviest boats = 0
3. While left ≤ right:
   • If people[left] + people[right] ≤ limit:
     • pair them → left++
   • Always move right– because heaviest boards boat
   • boats++
4. Return boats

This guarantees minimal number of boats.

---

4. Time and Space Complexity

Time Complexity:

O(N log N)

due to sorting

Space Complexity:

O(1)

sorting can be done in-place

---

5. Java Solution

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);

        int left = 0;
        int right = people.length - 1;
        int boats = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;   // they share a boat
            }
            right--;       // heaviest always boards
            boats++;
        }

        return boats;
    }
}

---

6. Dry Run Examples

Example 1

Input:

people = [3,2,2,1]
limit = 3

Sorted:

[1,2,2,3]

Pairs:

• 1 + 3 > 3 → 3 alone (boats=1)
• 1 + 2 ≤ 3 → pair (boats=2)
• 2 alone (boats=3)

Output:

3

---

Example 2

Input:

people = [3,5,3,4]
limit = 5

Sorted:

[3,3,4,5]

Process:

• 3 + 5 > 5 → 5 alone (boats=1)
• 3 + 4 > 5 → 4 alone (boats=2)
• 3 + 3 ≤ 5 → pair (boats=3)

Output:

3

---

Example 3

Input:

people = [1,2]
limit = 3

1 + 2 = 3 → pair

Output:

1

---

Example 4

Input:

people = [5,5,5]
limit = 5

Each must go alone

Output:

3

---

Example 5

Input:

people = [2,2,2,2]
limit = 3

No two can pair → all separate

Output:

4

---

7. Why This Solution Works

• Sorting lets us reason about optimal pairing
• Pairing heaviest with lightest minimizes unused capacity
• Each decision optimally reduces remaining candidates
• Two-pointer strategy ensures linear scan after sorting
• Never need to reconsider earlier choices
• Proven optimal via greedy correctness reasoning

---

8. Common Mistakes

1. Trying to use dynamic programming (unnecessary)
2. Pairing two lightest or two heaviest first
3. Forgetting boat limit applies to sum, not individual weight
4. Using more than two per boat
5. Counting invalid pair attempts as boats