881. Boats to Save People
Explanation:
To solve this problem, we can follow these steps:
- Sort the array of people in non-decreasing order.
- Use two pointers, one starting from the beginning and the other starting from the end of the array.
- While the two pointers don't overlap, check if the sum of weights of the two persons pointed by the pointers is less than or equal to the limit. If yes, increment both pointers. If not, increment only the end pointer.
- Increment the boat count each time we pair up people or when we have a single person in the boat.
- Continue this process until both pointers overlap.
The time complexity of this solution is O(nlogn) due to the sorting step, where n is the number of people. The space complexity is O(1) as we are using constant extra space.
:
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int boats = 0;
int i = 0;
int j = people.length - 1;
while (i <= j) {
if (people[i] + people[j] <= limit) {
i++;
}
j--;
boats++;
}
return boats;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.