Problem Description

You have an array people where each element people[i] represents the weight of the i-th person. You also have an infinite number of boats available, and each boat has a maximum weight capacity called limit.

Each boat can carry at most 2 people at the same time, but only if their combined weight doesn't exceed the limit.

Your task is to find the minimum number of boats needed to carry all the people.

For example, if people = [1, 2] and limit = 3, you can put both people in one boat since 1 + 2 = 3 ≤ limit, so you need only 1 boat.

If people = [3, 2, 2, 1] and limit = 3, you would need 3 boats:

• Boat 1: person with weight 3 (alone, since 3 + any other weight > 3)
• Boat 2: person with weight 2 and person with weight 1 (combined weight = 3)
• Boat 3: person with weight 2 (alone)

The key constraints are:

• Each boat can hold at most 2 people
• The total weight in a boat cannot exceed limit
• You want to minimize the total number of boats used

Intuition

The key insight is that we want to pair the heaviest person with the lightest person whenever possible. Why? Because if the heaviest person can't fit with the lightest person, they definitely can't fit with anyone else and must go alone.

Think about it this way: if we sort the people by weight, we get something like [light, ..., heavy]. The heaviest person has the least flexibility - they can only potentially pair with lighter people. The lightest person has the most flexibility - they can potentially pair with anyone.

So we use a greedy strategy:

1. Try to pair the heaviest remaining person with the lightest remaining person
2. If they can fit together (sum ≤ limit), great! Put them both in one boat
3. If they can't fit together, the heavy person must go alone

This naturally leads to a two-pointer approach after sorting:

• Start with pointers at both ends of the sorted array
• If people[left] + people[right] ≤ limit, we can pair them, so move both pointers inward
• If people[left] + people[right] > limit, the heavier person goes alone, so only move the right pointer inward
• Each iteration uses exactly one boat

Why is this optimal? Because we're maximizing the number of 2-person boats. Every time we successfully pair people, we save a boat. By always trying to pair the extremes (heaviest with lightest), we give ourselves the best chance of creating valid pairs throughout the process.

Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

The implementation uses a greedy algorithm combined with the two-pointer technique:

Step 1: Sort the array

people.sort()

First, we sort the people array in ascending order. This allows us to easily access the lightest person (at the beginning) and the heaviest person (at the end).

Step 2: Initialize variables

ans = 0
i, j = 0, len(people) - 1

• ans keeps track of the number of boats used
• i is the left pointer starting at index 0 (lightest person)
• j is the right pointer starting at the last index (heaviest person)

Step 3: Process people using two pointers

while i <= j:
    if people[i] + people[j] <= limit:
        i += 1
    j -= 1
    ans += 1

The main loop continues while i <= j, meaning there are still people to process:

• Check if the lightest and heaviest remaining people can share a boat: people[i] + people[j] <= limit
  • If yes, both people board the boat, so we move the left pointer right (i += 1) and the right pointer left (j -= 1)
  • If no, only the heavier person boards (alone), so we only move the right pointer left (j -= 1)
• In either case, we use one boat, so increment ans += 1

Why this works:

• Each iteration processes at least one person (the heavier one at position j)
• When two people can share a boat, we process both in one iteration
• When the pointers meet or cross (i > j), all people have been assigned to boats

Time Complexity: O(n log n) due to sorting, where n is the number of people Space Complexity: O(1) if we don't count the space used by sorting

Example Walkthrough

Let's walk through the solution with people = [5, 1, 4, 2] and limit = 6.

Step 1: Sort the array After sorting: people = [1, 2, 4, 5]

Step 2: Initialize pointers and boat counter

• i = 0 (pointing to weight 1)
• j = 3 (pointing to weight 5)
• ans = 0 (no boats used yet)

Step 3: Process with two pointers

Iteration 1:

• Check: Can person at i=0 (weight 1) and person at j=3 (weight 5) share a boat?
• people[0] + people[3] = 1 + 5 = 6 ≤ 6 ✓ Yes, they can share!
• Action: Move both pointers inward (i = 1, j = 2) and use one boat (ans = 1)
• Boat 1: [1, 5]

Iteration 2:

• Check: Can person at i=1 (weight 2) and person at j=2 (weight 4) share a boat?
• people[1] + people[2] = 2 + 4 = 6 ≤ 6 ✓ Yes, they can share!
• Action: Move both pointers inward (i = 2, j = 1) and use one boat (ans = 2)
• Boat 2: [2, 4]

Loop ends: i > j (2 > 1), so all people have been assigned.

Result: We need 2 boats to carry all 4 people.

Let's trace through one more example where not everyone can pair up: people = [3, 5, 3, 4] and limit = 5.

After sorting: people = [3, 3, 4, 5]

• i = 0, j = 3, ans = 0

Iteration 1: 3 + 5 = 8 > 5 ✗ Can't share. Person with weight 5 goes alone. (j = 2, ans = 1)

Iteration 2: 3 + 4 = 7 > 5 ✗ Can't share. Person with weight 4 goes alone. (j = 1, ans = 2)

Iteration 3: 3 + 3 = 6 > 5 ✗ Can't share. Person with weight 3 goes alone. (j = 0, ans = 3)

Iteration 4: i = j = 0. Last person (weight 3) goes alone. (j = -1, ans = 4)

Result: We need 4 boats (everyone goes alone since no valid pairs exist).

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array people. This is dominated by the sorting operation people.sort(), which takes O(n × log n) time. The subsequent while loop with two pointers traverses the array once in O(n) time, but this is overshadowed by the sorting complexity.

The space complexity is O(log n). Although the algorithm itself only uses a constant amount of extra space for variables like ans, i, and j, the sorting operation typically requires O(log n) space for the recursion stack in efficient sorting algorithms like Quicksort or the temporary space used in Timsort (Python's default sorting algorithm).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Sort the Array

Problem: A common mistake is attempting to use the two-pointer technique without first sorting the array. The algorithm relies on having the lightest person at one end and the heaviest at the other.

Incorrect approach:

def numRescueBoats(self, people: List[int], limit: int) -> int:
    # Missing people.sort()!
    boat_count = 0
    left = 0
    right = len(people) - 1
  
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        boat_count += 1
  
    return boat_count

Why it fails: Without sorting, people[left] isn't necessarily the lightest remaining person, and people[right] isn't the heaviest. This leads to suboptimal pairing and potentially incorrect results.

Solution: Always sort the array first before applying the two-pointer technique.

Pitfall 2: Trying to Fit More Than Two People Per Boat

Problem: Misunderstanding the constraint that each boat can hold at most 2 people, not as many as the weight limit allows.

Incorrect approach:

def numRescueBoats(self, people: List[int], limit: int) -> int:
    people.sort()
    boat_count = 0
    i = 0
  
    while i < len(people):
        current_weight = people[i]
        people_in_boat = 1
        i += 1
      
        # Wrong: trying to add more than one additional person
        while i < len(people) and current_weight + people[i] <= limit:
            current_weight += people[i]
            people_in_boat += 1
            i += 1
      
        boat_count += 1
  
    return boat_count

Why it fails: This attempts to pack as many people as possible into each boat based on weight, ignoring the 2-person maximum capacity constraint.

Solution: Remember that each boat holds at most 2 people, regardless of their combined weight.

Pitfall 3: Incorrect Pointer Movement Logic

Problem: Moving both pointers in all cases, or only moving one pointer regardless of whether two people board.

Incorrect approach:

def numRescueBoats(self, people: List[int], limit: int) -> int:
    people.sort()
    boat_count = 0
    left = 0
    right = len(people) - 1
  
    while left <= right:
        if people[left] + people[right] <= limit:
            # Wrong: moving both pointers even when they can share
            pass
      
        # Always moving both pointers
        left += 1
        right -= 1
        boat_count += 1
  
    return boat_count

Why it fails: This incorrectly assumes we always process two people per iteration, which isn't true when the heaviest person must ride alone.

Solution: Only move the left pointer when the lightest and heaviest can share a boat. Always move the right pointer since the heaviest person always boards.