TIP102 Unit 3 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
creatures
where each element represents the magical power of a creature, and an integer limit
representing the maximum magical load a boat can carry.limit
.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
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