Is Boats to Save People easy or hard?

Boats to Save People is rated Medium difficulty. The implementation is straightforward once the greedy insight is recognized, but many candidates initially miss the idea of pairing the lightest and heaviest people after sorting.

How to solve Boats to Save People in O(n)?

A pure O(n) solution is not possible for the general case because the people array is unsorted and must be ordered to apply the greedy pairing logic. After sorting, the pairing step itself runs in O(n) using two pointers that move toward the center of the array.

Boats to Save People Python or Java solution?

Most implementations follow the same steps: sort the array, initialize two pointers at the start and end, and increment a boat counter while adjusting pointers based on whether the pair fits within the limit. This logic is easily implemented in Python, Java, C++, JavaScript, and C#.

What is the best approach for Boats to Save People?

The optimal solution uses a greedy strategy with sorting and two pointers. Sort the weights, then try pairing the lightest and heaviest people together. If their combined weight exceeds the limit, the heaviest person goes alone. This minimizes wasted capacity and runs in O(n log n) time with O(1) extra space.

Is Boats to Save People asked at Google/Amazon/Meta?

Boats to Save People is a common greedy and two-pointer interview question and has appeared in interviews at companies such as Amazon, Google, and Meta. It tests the ability to recognize greedy pairing strategies and apply sorting with two pointers efficiently.

What data structure is used in Boats to Save People?

The solution mainly relies on arrays and the two-pointer technique after sorting. No advanced data structures are required. The algorithm works by scanning the sorted array from both ends and greedily pairing people.

What is the time complexity of Boats to Save People?

The time complexity is O(n log n) because the array of weights must be sorted first. After sorting, the two-pointer scan runs in O(n) time. Space complexity is O(1) if sorting is done in place.

Description Solution Video 7:03

881. Boats to Save People

Medium62.7% acceptance11 companies

You are given an array people where people[i] is the weight of the i^th 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⁴
1 <= people[i] <= limit <= 3 * 10⁴

Asked at 11 companies

UiPath Sigmoid

IBM Amazon Flipkart Microsoft Bloomberg Snowflake Atlassian

Google Meta

Topics

7:03

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numRescueBoats(self, people: List[int], limit: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2]
3

Input

[3,2,2,1]
3

Input

[3,5,3,4]
5

Your code is saved on this device.Solution