Skip to content

11. Container With Most Water

🔗 Source:

Intuition

Give a list of number, find maximum volumn between two entries given that $$ \text{Volumn} = \min(\text{nums}[i],\text{nums}[j]) \times (j - i) $$ for \(0 \le i < j < \text{len}\)

Approach

Use Sliding Windows approach.

  • Step 1:
    • creat two pointer low and high pointing to the start and end position of the given array.
    • creat variable max to store the max value we ever get and keep updating max during loop iteration.
  • Step 2: During loop iteration,
    • If height[low] < height[high], move low pointer until current height is less than or equal to height[low].
    • If height[low] >= height[high], move high pointer until current height is less than or equal to height[height].
  • Hence, in every loop, we will get a higher height than the previous one. The loop iteration ends when two pointer encounters. Finally, we return the maximum value of volumn we get during iteration.

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxArea(int[] height) {
        int low = 0;
        int high = height.length - 1;
        int volumn = 0;
        int h = 0;
        while (low < high) {
            h = Math.min(height[low], height[high]);
            volumn = Math.max(h * (high - low), volumn);
            if (height[low] < height[high]) {
                low++;
                while(low < high && h > height[low]) { 
                    low++;
                }
                h = height[low];
            } else {
                high--;
                while(low < high && h > height[high]) { 
                    high--;
                }
                h = height[high];
            }
        }
        return volumn;
    }
}