Problem 48 - Boats to Save People

Explore our archive for previous posts.

Problem 47 - Largest Number At Least Twice of Others

Problem 46 - Reverse Linked List

Problem 45 - Middle of the Linked List

Question

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints:

• 1 <= people.length <= 5 * 10^4

• 1 <= people[i] <= limit <= 3 * 10^4

Approach

This problem involves finding the minimum number of boats needed to rescue a given number of people. Each boat has a weight limit, and you are given an array representing the weights of people. The goal is to pair people in the boats in such a way that the total weight in a boat is at most the limit.

The key to solving this problem lies in the efficient pairing of people in boats while minimizing the number of boats needed. Idea is to pair the heaviest person with the lightest person, optimizing the use of boat capacity.

Here's a high-level approach:

1. Sort the Weights:

   • Sort the array of weights in ascending order. Sorting simplifies the process of pairing people.

2. Use Two Pointers:

   • Initialize two pointers, left and right, pointing to the beginning and end of the sorted array, respectively.

3. Pair Heaviest with Lightest:

   • Pair the heaviest person (weights[right]) with the lightest person (weights[left]).

   • If the sum of their weights exceeds the boat limit, only the heaviest person can take the boat.

4. Move Pointers and Count Boats:

   • Move the pointers accordingly:

     • If both people can take the boat, move both pointers inward.

     • If only the heaviest person can take the boat, move only the right pointer.

   • Increment the boat count after each pairing.

5. Repeat Until Pointers Meet:

   • Repeat the process until the left and right pointers meet.

This approach ensures that each boat carries the heaviest person it can while maintaining a balance between weight and the boat limit.

Solution

Solve it here

import java.util.Arrays;

public class BoatsToSavePeople {

    public int numRescueBoats(int[] people, int limit) {
        // Sort the weights in ascending order
        Arrays.sort(people);

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

        // Pair people using two pointers
        while (left <= right) {
            // Pair the heaviest and lightest person if we can
            if (people[left] + people[right] <= limit) {
                left++;
                right--;  
            } else {
                // Just take the heaviest person if we can't take the lightest person alongside
                right--;
            }
         
            boats++; // Increment the boat count after each pairing
        }

        return boats;
    }
}

Time and space complexity

Time Complexity: The time complexity is dominated by the sorting operation, which takes O(n log n) time, where n is the length of the people array. The pairing process after sorting takes linear time, so the overall time complexity is O(n log n).

Space Complexity: The space complexity is O(1) because the algorithm uses only a constant amount of extra space regardless of the input size.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?

Other noteworthy newsletters

ByteByteGo system design

System design one newsletter

StrategizeYourCareer newsletter

Embedded Rustacean