Enchanted Boats - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The input is an array creatures where each element represents the magical power of a creature, and an integer limit representing the maximum magical load a boat can carry.
• Q: What is the output?
  • A: The output is an integer representing the minimum number of enchanted boats required to carry all the creatures.
• Q: What are the constraints on the boats?
  • A: Each boat can carry at most two creatures, and their combined magical power must not exceed the limit.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the creatures by their magical power, then use a two-pointer approach to pair the lightest and heaviest creatures together. If they can share a boat without exceeding the limit, move both pointers inward; otherwise, the heavier creature must go alone.

1. Sort the `creatures` array in ascending order.
2. Initialize two pointers, `left` at the start of the array and `right` at the end of the array, and a counter `boats` set to 0.
3. While `left` is less than or equal to `right`:
   1. If the sum of `creatures[left]` and `creatures[right]` is less than or equal to `limit`, increment `left` (both creatures can share a boat).
   2. Always decrement `right` (the rightmost creature is placed in a boat).
   3. Increment `boats` by 1.
4. Return the value of `boats` as the result.

⚠️ Common Mistakes

• Forgetting that each boat can carry at most two creatures.
• Not handling the case where creatures cannot be paired and must each have their own boat.

I-mplement

def num_enchanted_boats(creatures, limit):
    # Step 1: Sort the array of creatures' magical powers
    creatures.sort()

    left = 0
    right = len(creatures) - 1
    boats = 0

    # Step 2: Use two pointers to pair creatures
    while left <= right:
        # If the weakest and strongest creature can share a boat
        if creatures[left] + creatures[right] <= limit:
            left += 1  # Move the left pointer inward

        right -= 1  # Move the right pointer inward
        boats += 1  # One boat is used for this pair or for the single creature

    return boats

# Example usage
print(num_enchanted_boats([1, 2], 3))  # Output: 1
print(num_enchanted_boats([3, 2, 2, 1], 3))  # Output: 3
print(num_enchanted_boats([3, 5, 3, 4], 5))  # Output: 4