How do you solve Boats to Save People on LeetCode?

Boats to Save People (LeetCode #881) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting the array allows for efficient pairing of people.

What is the time complexity of Boats to Save People?

The optimal solution for Boats to Save People runs in O(n log n) time and uses O(1) space. The sorting step takes O(n log n), and the two-pointer traversal takes O(n), making this approach efficient overall.

What is the brute force solution for Boats to Save People?

The brute force approach for Boats to Save People is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we try every possible combination of people to see how many boats are needed. This means checking each pair of people to see if they can share a boat, which can be quite slow. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Boats to Save People?

Boats to Save People uses the following concepts: Array, Two Pointers, Greedy, Sorting. The recommended patterns to study are: Two Pointers, Greedy Algorithms.

What are the interview tips for Boats to Save People?

Always think about edge cases and test your code with them. Explain your thought process clearly while coding, as it shows your understanding. Practice similar problems to recognize patterns like the two-pointer technique.

What are common mistakes when solving Boats to Save People?

Not considering edge cases where all people are heavier than the limit. Forgetting to sort the array before applying the two-pointer technique.

#881

Boats to Save People

Medium

ArrayTwo PointersGreedySortingTwo PointersGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

In the optimal approach, we sort the array and use a two-pointer technique. This allows us to efficiently pair the lightest and heaviest people, minimizing the number of boats needed.

⚙️

Algorithm

4 steps

1Step 1: Sort the people array.
2Step 2: Initialize two pointers: one at the start (lightest) and one at the end (heaviest).
3Step 3: While the start pointer is less than or equal to the end pointer: - If the sum of the weights at both pointers is less than or equal to the limit, move both pointers inward (indicating they can share a boat). - If not, move only the end pointer inward (indicating the heavier person needs a separate boat). Step 4: Increment the boat counter each time you make a decision.
4Step 5: Return the total number of boats needed.

solution.py10 lines

1def numRescueBoats(people, limit):
2    people.sort()
3    boats = 0
4    left, right = 0, len(people) - 1
5    while left <= right:
6        if people[left] + people[right] <= limit:
7            left += 1
8        right -= 1
9        boats += 1
10    return boats

ℹ

Complexity note: The sorting step takes O(n log n), and the two-pointer traversal takes O(n), making this approach efficient overall.

1Sorting the array allows for efficient pairing of people.
2Using two pointers minimizes the number of boats needed by always trying to pair the lightest and heaviest person.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.