Container with Most Honey - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Two-pointer technique

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 function?

  • A: The input is an integer array height of length n, where each element represents the height of a vertical line at that position.

• Q: What is the expected output of the function?

  • A: The function should return the maximum amount of honey a container formed by two lines and the x-axis can store.

• Q: How is the amount of honey determined?

  • A: The amount of honey is determined by the area of the container, which is calculated as the width between the two lines multiplied by the height of the shorter line.

• Q: What should the function return if the input array is empty or has less than two lines?

  • A: If the array has fewer than two lines, the function should return 0 because no container can be formed.

• The function most_honey() should take an integer array representing the heights of vertical lines and return the maximum amount of honey (area) that can be contained between two lines. The area is determined by the distance between the two lines and the height of the shorter line.

HAPPY CASE
Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Expected Output: 49

EDGE CASE
Input: [1, 1]
Expected Output: 1

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use the two-pointer technique to maximize the area. Start with pointers at both ends of the array and move them inward based on the heights.

1. Initialize two pointers: `left` at the start (0) and `right` at the end (len(height) - 1) of the array.
2. Initialize `max_honey` to 0.
3. While `left` is less than `right`:
   a. Calculate the width as `right - left`.
   b. Calculate the current height as the minimum of `height[left]` and `height[right]`.
   c. Calculate the current area as `width * current_height`.
   d. Update `max_honey` if the `current_area` is larger.
   e. Move the pointers: increment `left` if `height[left]` is less than `height[right]`, otherwise decrement `right`.
4. Return `max_honey`

⚠️ Common Mistakes

• Forgetting to update the maximum area after each calculation.
• Incorrectly managing the pointer movements which may skip potential maximum areas.

I-mplement

Implement the code to solve the algorithm.

def most_honey(height):
    left = 0
    right = len(height) - 1
    max_honey = 0
    
    while left < right:
        # Calculate the width
        width = right - left
        # Calculate the height of the container, which is the minimum of the two heights
        current_height = min(height[left], height[right])
        # Calculate the area
        current_area = width * current_height
        # Update max_honey if the current_area is larger
        max_honey = max(max_honey, current_area)
        
        # Move the pointers
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_honey