Container's area

area = heigt * width

A container in this problem has two heights. According to Liebig's law of the minimum, the smaller height should be selected to calculate the area.

i and j is the index of the input

function area(i, j)
   return MIN(height[i], height[j]) * ABS(i - j)
   

Maximizing the area

Maybe, sometimes, I'd to brute force every pair of i and j.

max = MIN_VALUE

foreach i in heights
   foreach j in heights
     
     max = MAX(area(i,j), max)

Using brain

Needless comparing

Instead of brute force each i and j, we can choose the next i or j which may cause the area bigger.

take a look at MIN(height[i], height[j]) * ABS(i - j), when the enumeration is like

foreach i = 0 -> end
   foreach j = end -> 0
     
      max = MAX(area(i,j), max)

the i and j are getting closer, so the only factor is MIN(height[i], height[j]). Attempting to compare the heights smaller than MIN(height[i], height[j]) are needless.

Redundant enumeration

After i and j meet each other, the rest of enumeration are redundant. so improved version should be like

foreach i = 0 -> end
   foreach j = end -> i
     
      max = MAX(area(i,j), max)

now, lets see what happens when i moves to i + 1 and j remains the same.

height[i] > height[j] and height[i + 1] < height[j]    
   MIN(height[i], height[j])     = height[j]
   MIN(height[i + 1], height[j]) = height[i + 1]
   
   area's height is getting smaller


height[i] > height[j] and height[i + 1] > height[j]    
   MIN(height[i], height[j])     = height[j]
   MIN(height[i + 1], height[j]) = height[j]
   
   area's height  remains the same
   

height[i] < height[j] and height[i + 1] < height[j]
    MIN(height[i], height[j])     = height[i]
    MIN(height[i + 1], height[j]) = MIN(height[i], height[i + 1])
    
    area's height  is getting smaller
    
    
height[i] < height[j] and height[i + 1] > height[j]
    MIN(height[i], height[j])     = height[i]
    MIN(height[i + 1], height[j]) = height[j]
    
    area's height is getting bigger
    

as you can see only height[i] < height[j], then i moves to i + 1 might generate a bigger area. this also applies to j moves to j - 1.

Now, our greedy code goes as following

i = 0
j = end

while i and j not meet
   
   max = MAX(area(i,j), max)

   if height[i] < height[j]
      i = i + 1
   
   if height[i] > height[j]
      j = j - 1