algoadvance

You are given an array people where people[i] is the weight of the ith person, and an integer limit representing the weight limit of a boat. Each boat can carry at most two people at the same time, provided the sum of the weights of those people is at most limit.

Return the minimum number of boats to carry every person.

Clarifying Questions

  1. Q: Are the number of people, N, and the weights always positive integers?
    • A: Yes, N and weights are positive integers.
  2. Q: Can a person be placed in multiple boats?
    • A: No, each person must be carried exactly once.
  3. Q: What to do if a single person’s weight is greater than the limit?
    • A: According to the problem constraints, this edge case should not occur. Every person’s weight will be at most equal to the limit.

Strategy

The problem can be effectively solved using a two-pointer technique combined with sorting:

  1. Sort the array people to organize the weights.
  2. Use two pointers, one starting from the lightest person (left at index 0) and the other from the heaviest person (right at index len(people) - 1).
  3. Check if the lightest and heaviest person can share a boat (i.e., if their combined weight is less than or equal to limit). If they can, move both pointers inward; if they can’t, move only the right pointer inward as the heaviest person will need a separate boat.
  4. Continue this process until all people are assigned to boats.
  5. The number of moves made corresponds to the number of boats required.

Code

def numRescueBoats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1  # This person can share the boat
        right -= 1
        boats += 1  # A boat is used
    
    return boats

Explanation

  1. Sorting: The people array is sorted, which helps easily pair the lightest and heaviest people.
  2. Two Pointers: The left pointer starts at the beginning (lightest person) and the right pointer starts at the end (heaviest person).
  3. Check and Move Pointers:
    • If the sum of weights at left and right is within the boat limit, increment the left pointer (indicating this person is on the boat).
    • Always decrement the right pointer (indicating the heaviest person is accounted for).
  4. Boats Count: Increment the boats count for each valid operation (moving in the pointers).

Time Complexity

  1. Sorting: O(N log N)
  2. Two-Pointer Scan: O(N)

Thus, the overall time complexity is O(N log N) due to the sorting step. The two-pointer scan is linear in complexity afterward, which is efficient for most practical input sizes.

Try our interview co-pilot at AlgoAdvance.com