Leetcode#11

Container With Most Water

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Golang Solution

• This is a problem of finding max area of a rectangle.
• Use two pointer approach

// [1,8,6,2,5,4,8,3,7]
//  1,2,3,4,5,6,7,8,9

// Min(1,7) = 1  , 9-1 = 8 , Total = 8  max = 8
// Min(8,7) = 7  , 9-2 = 7 , Total = 49 max = 49. ---------
// Min(8,3) = 3  , 8-2 = 6 , Total = 18 max = 49
// Min(8,8) = 8  , 7-2 = 5 , Total = 40 max = 49
// Min(6,8) = 6  , 7-3 = 4 , Total = 24 max = 49
// Min(2,8) = 2  , 7-4 = 3 , Total = 6 max = 49

func maxArea(arr []int) int {
	if len(arr) == 0 || len(arr) == 1 {
		return 0
	}

	n := len(arr)
	leftIndex := 0
	rightIndex := n - 1

	maxWater := 0
	totalWater := 0
	for leftIndex < rightIndex {
		// calculate area of rectangle
		totalWater = min(arr[rightIndex], arr[leftIndex]) * (rightIndex - leftIndex)
		maxWater = max(maxWater, totalWater)
		
		// update pointers
		if arr[leftIndex] < arr[rightIndex] {
			leftIndex++
		} else {
			rightIndex--
		}
	}

	return maxWater
}

Output

Input
height = [1,8,6,2,5,4,8,3,7]

Output
49

Please visit https: https://codeandalgo.com for more such contents