Container with Most Honey

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.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• 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