LeetCode 881: Boats to Save People Solution
Master LeetCode problem 881 (Boats to Save People), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
881. Boats to Save People
Problem Explanation
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.
:
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 881 (Boats to Save People)?
This page provides optimized solutions for LeetCode problem 881 (Boats to Save People) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 881 (Boats to Save People)?
The time complexity for LeetCode 881 (Boats to Save People) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 881 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 881 in Java, C++, or Python.