Container With Most Water - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Container With Most Water" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers, Greedy

Introduction

The "Container With Most Water" problem requires finding two lines in an array that form the largest container with the x-axis. The solution must efficiently compute the maximum area without brute-forcing all possible pairs.

Problem Analysis

Given an array of heights, each element represents a vertical line at that index. The goal is to maximize the area formed by two lines and the x-axis. The area is calculated as the distance between the lines multiplied by the shorter of the two heights. For example, in [1,8,6,2,5,4,8,3,7], the max area is between indices 1 and 8 (height[1]=8, height[8]=7), yielding 7 * (8-1) = 49.

Solution Approach

The optimal solution uses the two-pointer technique. Start with pointers at both ends of the array. Calculate the area and move the pointer pointing to the shorter line inward, as moving the taller line cannot yield a larger area. Repeat until the pointers meet.

Go Implementation


func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0
    for left < right {
        currentHeight := min(height[left], height[right])
        currentWidth := right - left
        currentArea := currentHeight * currentWidth
        if currentArea > maxArea {
            maxArea = currentArea
        }
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. The two-pointer approach ensures each element is visited once. Space Complexity: O(1), as only constant extra space is used.

Testing and Examples

Test Case 1: Input [1,8,6,2,5,4,8,3,7] should return 49. Test Case 2: Input [1,1] should return 1. Edge Case: Input [1,100,100,1] should return 100.

Best Practices and Tips

Always initialize pointers at both ends for the two-pointer technique. Track the maximum area during each iteration. Avoid brute-force solutions to ensure optimal performance for large inputs.

Read more