Jobs

Interviews

Discussions

Boats to Save People

Medium

UiPath

3 views

Topics:

ArraysTwo PointersGreedy Algorithms

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
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 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴

Try coding it in LeetCode

Boats to Save People

Medium

UiPath

3 views

Topics:

ArraysTwo PointersGreedy Algorithms

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 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the weight of each person, and the limit of each boat?
Can the people array be empty, or can a person's weight be zero?
If it's not possible to save all people given the weight limit, should I return an error code, throw an exception, or is it guaranteed that a solution always exists?
Are the weights in the people array integers?
If multiple valid solutions exist (different pairings of people in boats), is any valid solution acceptable, or is there a specific criterion for optimality beyond minimizing the boat count?

Brute Force Solution

Approach

We want to find the minimum number of boats needed to rescue everyone, given that each boat can carry at most two people and has a weight limit. The brute force approach will try every possible combination of pairing people together in boats and then calculate the number of boats needed for that specific pairing.

Here's how the algorithm would work step-by-step:

Consider every single possible way to group the people together, remembering that each boat can have at most two people.
For each of these groupings, check if the weight of each boat is within the weight limit.
If any boat is over the weight limit, that grouping is not a valid solution, so discard it.
For each grouping that is valid (meaning all boats are within the weight limit), count the number of boats used.
After checking all possible groupings, find the grouping that uses the fewest number of boats. This is the answer.

Code Implementation

from itertools import combinations

def boats_to_save_people_brute_force(people, limit):
    number_of_people = len(people)
    minimum_number_of_boats = number_of_people + 1

    # Iterate through all possible combinations of pairings
    for i in range(number_of_people + 1):
        for combination in combinations(range(number_of_people), i):
            boats = []
            unpaired_people = list(range(number_of_people))

            # Create pairs based on the current combination
            for index in combination:
                if index in unpaired_people:
                    unpaired_people.remove(index)

            for index_one in combination:
                for index_two in unpaired_people:
                    if people[index_one] + people[index_two] <= limit:
                        boats.append((people[index_one], people[index_two]))
                        unpaired_people.remove(index_two)
                        break

            # All remaining people need a boat of their own
            for alone_index in unpaired_people:
                boats.append((people[alone_index],))

            valid_solution = True
            for boat in boats:
                boat_weight = sum(boat)
                if boat_weight > limit:
                    valid_solution = False
                    break

            # Check for a better solution
            if valid_solution:
                number_of_boats_needed = len(boats)

                # Update the minimum number of boats needed
                if number_of_boats_needed < minimum_number_of_boats:
                    minimum_number_of_boats = number_of_boats_needed

    if minimum_number_of_boats == number_of_people + 1:
        return -1  # No valid solution found
    else:
        return minimum_number_of_boats

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach considers every possible subset of people to pair together in boats. Generating all subsets of a set of n people has a time complexity of O(2^n). For each of these subsets, we need to check if the weight of each boat (pair of people or single person) is within the limit. This involves iterating through the subset, which in the worst case can be of size n, therefore taking O(n) time. Combining these two aspects, the overall time complexity becomes O(2^n * n).

Space Complexity

O(2^N) – The brute force approach considers every possible way to group the N people. Generating all possible groupings where each person can either be alone or paired with another person leads to exploring a tree-like structure. In the worst case, this structure can have a branching factor that results in exploring a number of combinations that grows exponentially with N. Thus, the space needed to store these groupings, even temporarily during the recursive exploration, grows as O(2^N).

Optimal Solution

Approach

The goal is to minimize the number of boats needed to rescue people, given that each boat can carry at most two people and has a weight limit. The optimal strategy involves pairing the lightest person with the heaviest person possible, which is done repeatedly until everyone is rescued.

Here's how the algorithm would work step-by-step:

First, sort the people by their weight from lightest to heaviest.
Then, use two pointers: one pointing to the lightest person and the other pointing to the heaviest person.
Check if the lightest and heaviest person can fit in the same boat, meaning their combined weight is less than or equal to the boat's weight limit.
If they can fit together, pair them in the same boat and move both pointers inward (the light person moves to the next heavier person, and the heavy person moves to the next lighter person).
If they cannot fit together, it means the heaviest person needs a boat to themselves. Put the heaviest person in a boat, and move the heavy person pointer inward to the next lighter person.
Keep doing this until all the people are assigned to boats. The number of boats used is the solution.

Code Implementation

def numRescueBoats(people, limit):
    people.sort()

    left_pointer = 0
    right_pointer = len(people) - 1
    number_of_boats = 0

    while left_pointer <= right_pointer:
        # If the lightest and heaviest can share a boat
        if people[left_pointer] + people[right_pointer] <= limit:

            left_pointer += 1
            right_pointer -= 1

        # Heaviest person must take a boat alone
        else:
            right_pointer -= 1

        number_of_boats += 1

    return number_of_boats

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the people array, which takes O(n log n) time. After sorting, we use two pointers to iterate through the sorted array. The two-pointer approach iterates through the array at most once, taking O(n) time. Since O(n log n) is asymptotically greater than O(n), the overall time complexity is determined by the sorting step. Therefore, the time complexity of the algorithm is O(n log n).

Space Complexity

O(1) – The provided solution primarily utilizes two pointers, which occupy constant space regardless of the number of people. Sorting the input array is done in-place, so it does not contribute to auxiliary space. Consequently, the auxiliary space used by the algorithm is independent of the input size N, where N is the number of people. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty people array	Return 0, as no people need to be saved.
People array with one person	Return 1, as a single person always needs one boat.
All people have the same weight, and it exceeds the limit.	Return the length of the people array, as each person needs a separate boat.
The lightest two people exceed the limit.	Each person will require their own boat so the algorithm must return the length of the people array.
The heaviest person exceeds the limit.	The heaviest person must have a boat to themselves; the algorithm should handle this by iterating through people from heaviest to lightest, pairing where possible.
People array is already sorted	Algorithm should still execute and produce correct output, even if the input is pre-sorted; pre-sort the people array before processing.
People array contains a wide range of weights.	The algorithm should correctly pair heaviest and lightest people within the weight limit, regardless of the range.
Weight limit is smaller than smallest person's weight	Handle this edge case by returning the array size because each person will need their own boat.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the weight of each person, and the limit of each boat?
Can the people array be empty, or can a person's weight be zero?
If it's not possible to save all people given the weight limit, should I return an error code, throw an exception, or is it guaranteed that a solution always exists?
Are the weights in the people array integers?
If multiple valid solutions exist (different pairings of people in boats), is any valid solution acceptable, or is there a specific criterion for optimality beyond minimizing the boat count?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every single possible way to group the people together, remembering that each boat can have at most two people.
For each of these groupings, check if the weight of each boat is within the weight limit.
If any boat is over the weight limit, that grouping is not a valid solution, so discard it.
For each grouping that is valid (meaning all boats are within the weight limit), count the number of boats used.
After checking all possible groupings, find the grouping that uses the fewest number of boats. This is the answer.

Code Implementation

from itertools import combinations

def boats_to_save_people_brute_force(people, limit):
    number_of_people = len(people)
    minimum_number_of_boats = number_of_people + 1

    # Iterate through all possible combinations of pairings
    for i in range(number_of_people + 1):
        for combination in combinations(range(number_of_people), i):
            boats = []
            unpaired_people = list(range(number_of_people))

            # Create pairs based on the current combination
            for index in combination:
                if index in unpaired_people:
                    unpaired_people.remove(index)

            for index_one in combination:
                for index_two in unpaired_people:
                    if people[index_one] + people[index_two] <= limit:
                        boats.append((people[index_one], people[index_two]))
                        unpaired_people.remove(index_two)
                        break

            # All remaining people need a boat of their own
            for alone_index in unpaired_people:
                boats.append((people[alone_index],))

            valid_solution = True
            for boat in boats:
                boat_weight = sum(boat)
                if boat_weight > limit:
                    valid_solution = False
                    break

            # Check for a better solution
            if valid_solution:
                number_of_boats_needed = len(boats)

                # Update the minimum number of boats needed
                if number_of_boats_needed < minimum_number_of_boats:
                    minimum_number_of_boats = number_of_boats_needed

    if minimum_number_of_boats == number_of_people + 1:
        return -1  # No valid solution found
    else:
        return minimum_number_of_boats

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, sort the people by their weight from lightest to heaviest.
Then, use two pointers: one pointing to the lightest person and the other pointing to the heaviest person.
Check if the lightest and heaviest person can fit in the same boat, meaning their combined weight is less than or equal to the boat's weight limit.
If they can fit together, pair them in the same boat and move both pointers inward (the light person moves to the next heavier person, and the heavy person moves to the next lighter person).
If they cannot fit together, it means the heaviest person needs a boat to themselves. Put the heaviest person in a boat, and move the heavy person pointer inward to the next lighter person.
Keep doing this until all the people are assigned to boats. The number of boats used is the solution.

Code Implementation

def numRescueBoats(people, limit):
    people.sort()

    left_pointer = 0
    right_pointer = len(people) - 1
    number_of_boats = 0

    while left_pointer <= right_pointer:
        # If the lightest and heaviest can share a boat
        if people[left_pointer] + people[right_pointer] <= limit:

            left_pointer += 1
            right_pointer -= 1

        # Heaviest person must take a boat alone
        else:
            right_pointer -= 1

        number_of_boats += 1

    return number_of_boats

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty people array	Return 0, as no people need to be saved.
People array with one person	Return 1, as a single person always needs one boat.
All people have the same weight, and it exceeds the limit.	Return the length of the people array, as each person needs a separate boat.
The lightest two people exceed the limit.	Each person will require their own boat so the algorithm must return the length of the people array.
The heaviest person exceeds the limit.	The heaviest person must have a boat to themselves; the algorithm should handle this by iterating through people from heaviest to lightest, pairing where possible.
People array is already sorted	Algorithm should still execute and produce correct output, even if the input is pre-sorted; pre-sort the people array before processing.
People array contains a wide range of weights.	The algorithm should correctly pair heaviest and lightest people within the weight limit, regardless of the range.
Weight limit is smaller than smallest person's weight	Handle this edge case by returning the array size because each person will need their own boat.