Boats to Save People - Minimizing Boats with Greedy Two-Pointers (Java)

We're navigating a scenario that beautifully combines sorting with a clever greedy two-pointer strategy: "Boats to Save People" (LeetCode #881).

This problem challenges us to minimize the number of boats used to rescue people with varying weights, given a boat's weight limit and capacity. Let's explore how we can efficiently get everyone to safety!

Understanding the Problem:

You are given an array people, where people[i] is the weight of the i-th person. You also have an infinite number of boats, each with a maximum limit for total weight. Crucially, each boat can carry at most two people at the same time, provided their combined weight does not exceed limit.

Our goal is to return the minimum number of boats required to carry every person.

Key Constraints/Rules:

• Each boat has a limit.

• Each boat can carry at most two people.

• The sum of weights of people in a boat must be <= limit.

• We need the minimum number of boats.

Example:

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

• Output: 3

  • Explanation:

    • Boat 1: (1, 2) -> 1+2 = 3 <= limit (valid)

    • Boat 2: (2) -> 2 <= limit (valid)

    • Boat 3: (3) -> 3 <= limit (valid)

    • Total 3 boats.

  • Alternatively: If you try (3, empty) -> 1 boat, then (2, empty) -> 1 boat, then (2,1) -> 1 boat. Still 3.

  • Consider an alternative scenario: If people = [5, 1, 2, 6], limit = 7

    • Sorting: [1, 2, 5, 6]

    • Pair (1, 6): 1+6 = 7 <= limit. 1 boat used. People [2, 5] remain.

    • Pair (2, 5): 2+5 = 7 <= limit. 1 boat used. No people remain.

    • Total 2 boats.

---

My Thought Process & Approach (Sorting + Greedy Two-Pointers):

The core of this problem is to minimize the number of boats. Since each boat can take at most two people, we should always try to pair people up. When we can't pair two, someone must go alone.

This immediately brings up the idea of a greedy strategy: How do we make the "best" decision at each step to ensure we use the fewest boats overall?

1. The Heaviest Person: The heaviest person people[j] must get on a boat. There's no way around it. So, for every heaviest person, we'll need at least one boat.

2. Pairing Strategy: To minimize boats, we should try to pair this heaviest person with someone. Who is the best candidate? The lightest person people[i].

   • Why the lightest? Because if people[j] can't go with people[i], they certainly can't go with anyone heavier than people[i]. So, people[j] would have to go alone.

   • If people[j] can go with people[i] (i.e., people[i] + people[j] <= limit), then we should definitely put them together. This saves a boat compared to sending people[j] alone and then people[i] alone later.

3. Sorting as Preprocessing: To easily access the lightest and heaviest people at any given moment, we should sort the people array. Once sorted, the lightest person is at people[0] (or people[i]) and the heaviest is at people[n-1] (or people[j]).

4. Two-Pointers: With the sorted array, we can use two pointers: i starting from the beginning (lightest person) and j starting from the end (heaviest person).

The Algorithm Steps:

1. Sort the people array in ascending order.

2. Initialize i = 0 (pointer to the lightest unboarded person) and j = n - 1 (pointer to the heaviest unboarded person).

3. Initialize cnt = 0 (number of boats used).

4. Loop while i <= j:

   • A boat is always used in this iteration: cnt++.

   • Check if the lightest person (people[i]) and the heaviest person (people[j]) can fit in the same boat: if (people[i] + people[j] <= limit).

     • If yes, they both get on. Move i forward (i++) to consider the next lightest person.

     • If no, the heaviest person (people[j]) must go alone. The lighter person (people[i]) stays to try and pair with a different (less heavy) person later.

   • In either case (whether a pair was formed or not), the heaviest person (people[j]) has been processed, so move j backward (j--) to consider the next heaviest person.

5. Once i > j, all people have been boarded. Return cnt.

This greedy strategy works because by always pairing the heaviest person with the lightest possible partner, we maximize the chances of sending two people per boat, thereby minimizing the total boat count.

---

Java Code Implementation:

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        int cnt =0;
        Arrays.sort(people);
        int i = 0;
        int j = n-1;
        while(i<=j){
            cnt++; 
            if(people[i]+people[j]<=limit){
                i++;
            }
            j--;
        }
        return cnt;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N log N)

  • The dominant operation is Arrays.sort(people), which takes O(N log N) time for an array of size N.

  • The while loop with two pointers runs for at most N iterations (since i and j move towards each other, covering each person once). Operations inside the loop are O(1).

  • Therefore, the overall time complexity is dominated by the sorting step: O(N log N).

• Space Complexity: O(N) (or O(log N) depending on sort implementation)

  • Arrays.sort() in Java for primitive arrays typically uses a Dual-Pivot Quicksort or Timsort, which can take O(log N) to O(N) auxiliary space in the worst case (for Timsort, it's typically O(N) for its merge passes).

  • The variables n, cnt, i, j use only O(1) additional space.