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.

• 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.

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.

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