NucuLabs.dev

Share this post

LeetCode: Boats to Save People

nuculabs.dev
Programming

LeetCode: Boats to Save People

Python3 and Rust solutions for the Leetcode problem Boats to Save People

Paula Rusti
and
Denis Nuțiu
Apr 8, 2023
Share

Hello everyone! 👋

Introduction

I’ve been practicing with some Leetcode daily challenges lately and since I’ve recently moved to Substack I wanted to make my first post here 😁

Thanks for reading NucuLabs.dev! Subscribe for free to receive new posts and support my work.

Boats to Save People

The problem Boats to Save People is solved using a Greedy approach.

Given a number of people and their weights, along with a carry limit for the boat.

You must find the number of boats needed to carry the people. A boat can carry a maximum of two people at a time.

To solve for this constraint, we would first sort the array containing the weights then attempt to pair the heaviest person with the lightest person. If their weight is below the or equal to the carry limit you remove the heaviest and lightest person from the list of people and add a count of one to the boats needed to carry people.

If you can’t make the pair, then you’ll put the heaviest person on the boat and start looking for another pair. You will also add one to the number of boats needed.

Rust Solution

impl Solution {
    pub fn num_rescue_boats(people: Vec<i32>, limit: i32) -> i32 {
        let mut i = 0;
        let mut j = people.len() - 1;
        let mut boats = 0;

        let mut sorted_people = people;
        sorted_people.sort_unstable();

        while i <= j {
            boats += 1;
            if sorted_people[i] + sorted_people[j] <= limit {
                i += 1
            }
            if j == 0 {
                break
            }
            j -= 1;
        }

        return boats;
    }
}

Python Solution

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people_size = len(people)
        if people_size == 1:
            return 1

        people.sort()
        boats_needed = 0
        i = 0
        j = people_size - 1
        while i <= j:
            # We found a pair of people
            if people[i] + people[j] <= limit:
                boats_needed += 1
                i += 1
                j -= 1
                continue

            j -= 1
            boats_needed += 1

        return boats_needed

Thanks for reading NucuLabs.dev! Subscribe for free to receive new posts and support my work.

Share
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 NucuLabs.dev
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing