Boats to Save People

Boats to Save People is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

Problem statement

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 104

- 1 <= people[i] <= limit <= 3 104

Topics and companies

Topics: Array, Two Pointers, Greedy, Sorting.

Reported in interviews at Amazon, Google, Paypal, Roblox.

How to practise Boats to Save People on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Boats to Save People in the code editor, or read the Boats to Save People editorial for a worked solution with its approach and complexity analysis.

Where Boats to Save People sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Boats to Save People

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Container With Most Water — Medium, same subpattern
• 4Sum — Medium, same subpattern
• Squares of a Sorted Array — Easy, same subpattern
• 3Sum Closest — Medium, same subpattern
• 3Sum Smaller — Medium, same subpattern
• 3Sum — Medium, same subpattern