What is the time complexity of Boats to Save People?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Boats to Save People?

This problem uses Array, Two Pointers, Greedy, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Boats to Save People?

Insight 1: Sorting the `people` array allows us to efficiently pair the lightest and heaviest people to maximize boat utilization. Insight 2: Using the two-pointer technique with a left and right pointer allows us to check for pairs efficiently after sorting.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Boats to Save People - LeetCode 881 Solution

Q: Which companies ask LeetCode 881. Boats to Save People in interviews?

This problem is frequently asked at Atlassian, Deutsche Bank, Docusign, Sigmoid, UiPath and 1 more companies.

Boats to Save People - Complete Solution Guide

Boats to Save People is LeetCode problem 881, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array people where people[i] is the weight of the i th 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 Explanati

Detailed Explanation

The problem asks us to find the minimum number of boats needed to save all people, given an array `people` representing the weight of each person, and a `limit` representing the maximum weight a boat can carry. Each boat can carry at most two people, as long as their combined weight does not exceed the `limit`. The input is an array of integers `people` and an integer `limit`. The output is an integer representing the minimum number of boats required.

Solution Approach

The solution uses a greedy approach combined with sorting and the two-pointer technique. First, the `people` array is sorted in ascending order. This allows us to efficiently pair the lightest and heaviest people. Two pointers, `left` and `right`, are initialized to the start and end of the sorted array, respectively. The algorithm iterates while `left` is less than or equal to `right`. In each iteration, it checks if the sum of the weights of the people at the `left` and `right` pointers is less than or equal to the `limit`. If it is, then both people can be placed in the same boat, and both pointers are moved. If it isn't, then the heaviest person (at the `right` pointer) must be placed in a boat alone, and only the `right` pointer is moved. In either case, the boat count is incremented.

Step-by-Step Algorithm

Step 1: Sort the `people` array in ascending order.
Step 2: Initialize `left` to 0 and `right` to `len(people) - 1`.
Step 3: Initialize `boats` to 0.
Step 4: While `left <= right`, do the following:
Step 5: If `people[left] + people[right] <= limit`, increment `left`.
Step 6: Decrement `right`.
Step 7: Increment `boats`.
Step 8: Return `boats`.

Key Insights

Insight 1: Sorting the `people` array allows us to efficiently pair the lightest and heaviest people to maximize boat utilization.
Insight 2: Using the two-pointer technique with a left and right pointer allows us to check for pairs efficiently after sorting.
Insight 3: The greedy approach of pairing the lightest person with the heaviest possible person is optimal for minimizing the number of boats.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Greedy, Sorting.

Companies

Asked at: Atlassian, Deutsche Bank, Docusign, Sigmoid, UiPath, Walmart Labs.

Boats to Save People | LeetCode 881

Medium

Array Two Pointers Greedy Sorting

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

Solution Code

Available in:

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int boats = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            boats++;
        }
        return boats;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 881: Boats to Save People - Detailed explanation and solution approaches.

Topics

Array Two Pointers Greedy Sorting

Companies

AtlassianDeutsche BankDocusignSigmoidUiPathWalmart Labs

Stats

Difficulty:Medium

Languages:4

Companies:6

Problem #:881

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Sort the `people` array in ascending order.
2
Step 2: Initialize `left` to 0 and `right` to `len(people) - 1`.
3
Step 3: Initialize `boats` to 0.
4
Step 4: While `left <= right`, do the following:
5
Step 5: If `people[left] + people[right] <= limit`, increment `left`.
6
Step 6: Decrement `right`.
7
Step 7: Increment `boats`.
8
Step 8: Return `boats`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is dominated by the sorting algorithm used, which is typically O(n log n). The space complexity is O(1) because the additional space used is constant, regardless of the input size, assuming an in-place sorting algorithm.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a HashMap (Counting)

Count the frequency of each weight using a HashMap. Iterate through the distinct weights and pair up people to fill the boats.

Time: O(n + k log k), where n is the number of people and k is the number of distinct weights.Space: O(k), where k is the number of distinct weights.

Trade-offs: This approach can be beneficial when the range of weights is much smaller than the number of people, resulting in fewer distinct weights. However, the overhead of using a HashMap might make it slower than the sorting approach in many cases.

✨

Key Insights

1Insight 1: Sorting the `people` array allows us to efficiently pair the lightest and heaviest people to maximize boat utilization.
2Insight 2: Using the two-pointer technique with a left and right pointer allows us to check for pairs efficiently after sorting.
3Insight 3: The greedy approach of pairing the lightest person with the heaviest possible person is optimal for minimizing the number of boats.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Greedy Algorithm

Making the best choice at each step without looking ahead.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Only one person: The algorithm correctly returns 1 because even a single person requires a boat. The loop `while left <= right` will run once.
Edge case 2: All people exceed half the limit: In this scenario, each person needs their own boat. The algorithm correctly handles this because the `if` condition will always be false, and the `right` pointer will decrement until `left > right`, resulting in the correct number of boats.
Edge case 3: Empty input: If `people` is empty, the algorithm correctly returns 0 as no boats are needed for 0 people. The `while` loop is not entered.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not sorting the `people` array: Failing to sort the array will lead to an incorrect greedy choice, resulting in a non-optimal number of boats.

✗Common mistake 2: Incorrectly incrementing the boat count: The boat count should be incremented in each iteration of the `while` loop, regardless of whether one or two people are assigned to the boat.

✗Common mistake 3: Not considering the case when `left` and `right` meet (single person): The `while left <= right` condition is crucial to handle cases where a single person remains. If the condition was `while left < right`, it might result in an undercount in those situations

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation with constraints: This problem is analogous to efficiently allocating resources with constraints, such as assigning tasks to workers with limited capacity.

🏦Real-world scenario 2: Load balancing: Optimizing the distribution of workload across multiple servers with a maximum load capacity can be seen as a variation of this problem.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 9, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Boats to Save People"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?