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 * 1041 <= people[i] <= limit <= 3 * 104In #881 Boats to Save People, each boat can carry at most two people with a total weight not exceeding a given limit. The goal is to minimize the number of boats needed to rescue everyone. A highly effective strategy combines sorting with the two pointers technique.
First, sort the array of people by weight. Then use two pointers: one starting at the lightest person and the other at the heaviest. If the combined weight of these two people is within the limit, they can share a boat, so move both pointers inward. Otherwise, the heaviest person must take a boat alone, and only the right pointer moves. Each step assigns exactly one boat.
This greedy strategy works because pairing the heaviest person with the lightest possible partner maximizes boat utilization. Sorting dominates the running time, giving a time complexity of O(n log n), while the two-pointer scan runs in O(n). The algorithm requires minimal extra space aside from sorting overhead.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy + Sorting + Two Pointers | O(n log n) | O(1) or O(log n) depending on sorting implementation |
NeetCode
This approach utilizes sorting and a two-pointer technique. By sorting the array, we simplify the pairing process, always trying to pair the lightest and heaviest person possible to fit within the limit. This method is greedy because it always tries to use the lightest and heaviest pair that fits to use fewer boats.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int numRescueBoats(int* people, int peopleSize, int limit) {
9 qsort(people, peopleSize, sizeof(int), compare);
10 int i = 0, j = peopleSize - 1;
11 int boats = 0;
12 while (i <= j) {
13 if (people[i] + people[j] <= limit) i++;
14 j--;
15 boats++;
16 }
17 return boats;
18}
19
20int main() {
21 int people[] = {3, 2, 2, 1};
22 int limit = 3;
23 printf("%d\n", numRescueBoats(people, 4, limit));
24 return 0;
25}Here, we first sort the array of people's weights. Then, using two pointers (one at the start and one at the end), we check if the lightest person (start) and the heaviest person (end) can share a boat. If they can, we move both pointers inward. If not, we move only the end pointer. We increment the boat count in each iteration. This ensures each person is considered.
In this approach, we again sort the weights, but the main focus is on maximizing each boat's capacity. If the heaviest person cannot be paired with the lightest one, they solely occupy a boat.
Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting allows us to efficiently match the lightest and heaviest people using a two-pointer technique. This helps determine whether two people can share a boat or if the heaviest must go alone.
Yes, this problem or its variations appear in coding interviews at companies like Amazon, Google, and Facebook. It tests understanding of greedy strategies, sorting, and two-pointer techniques.
No advanced data structure is required. An array with sorting and two pointer indices is sufficient to implement the greedy solution efficiently.
The optimal approach uses a greedy strategy with sorting and two pointers. After sorting the weights, pair the lightest and heaviest people when possible. If they exceed the limit, the heaviest person goes alone, ensuring the minimum number of boats.
The approach involves sorting and using a two-pointer technique. Comparing outer values ensures efficient pairing unless the limit constraint prohibits including the lighter weight, causing the heavy weight to proceed alone.