Start learning free

LESSON 233 OF 348 · TWO POINTERS

Container With Most Water in Kotlin: O(n) with Two Pointers

Practice O(n) Read the full explanation

You are given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i are (i, ai) and (i, 0). Find two lines, which together with the x-axis form a container, such that this container contains the most water.

Note: You may not slant the container and n is at least 2.

 

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

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · TWO POINTERS

    Container With Most Water in Kotlin, explained

    Problem overview

    The function maxArea receives an IntArray called height. Each element is the height of a vertical line, and the lines stand one unit apart along the x-axis. Choose two lines; together with the x-axis they form a container, and the water it holds is a rectangle. Return the largest amount of water any pair of lines can hold. The container can't be tilted, and there are at least two lines.

    For [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49. The lines of height 8 (at index 1) and 7 (at index 8) are 7 units apart, and the water level is capped by the shorter line, 7, so the area is 7 * 7 = 49.

    Approach: start wide, move the shorter line

    For any pair of positions left and right, the area is minOf(height[left], height[right]) * (right - left). Water above the shorter line would spill over it, so the shorter line sets the height. The brute force tries every pair and is O(n²).

    The faster idea starts with the widest container, using the first and last lines, and shrinks it from one side at a time. The question is which side to give up. Suppose the left line is the shorter one. Any container that keeps this left line and uses a closer right line is narrower, and its height is still capped by the left line, so it can't hold more than the current one. The left line has no better partner left, and it can be discarded. Moving the shorter pointer is therefore always safe, and moving the taller one can't help.

    Each step discards one line, so the pointers meet after at most n - 1 steps, and the whole scan is O(n).

    On the example, the first container uses 1 and 7 with width 8, giving area 8. The left line (1) is shorter, so left moves to the 8. The container of 8 and 7 has width 7 and area 49. The right line is the shorter one, so right moves, and no later container beats 49.

    Step by step

    1. Declare the state. result is the best area so far, starting at 0. left is 0 and right is height.size - 1. All three are vars.
    2. Loop while left < right. A container needs two different lines, so stop when the pointers meet.
    3. Compute the area. Take minOf the two heights, because the shorter line caps the water, and multiply by the width right - left.
    4. Keep the maximum. maxOf(result, area) means result never goes down.
    5. If the left line is shorter, do left++. Only a taller line in its place could possibly beat the current area.
    6. Otherwise do right--. Here the right line is no taller than the left one. When the heights are equal, moving either pointer is safe, and this branch moves the right.
    7. Return result.

    The solution in Kotlin

    class Solution {
    fun maxArea(height: IntArray): Int {
        var result = 0; var left = 0; var right = height.size - 1
        while (left < right) {
            val area = minOf(height[left], height[right]) * (right - left)
            result = maxOf(result, area)
            if (height[left] < height[right]) {
                left++
            } else {
                right--
            }
        }
        return result
    }
}

    Kotlin details worth knowing:

    • Semicolons. Kotlin doesn't need them, but they let several statements share one line, as in the first line of the function body. Putting each declaration on its own line is more common.
    • minOf and maxOf. These are standard functions that return the smaller or larger of two values.
    • size is a property. The last index is height.size - 1.
    • Int overflow. The area is an Int and wraps silently past about 2.1 billion. With 100000 lines that are each 100000 tall, the widest container holds 9999900000, which doesn't fit. If inputs can be that large, compute the area as a Long. The lesson's tests stay within Int.
    • if/else as a statement. Both branches only change a pointer, so nothing is returned from them.

    Complexity

    Time: O(n). Each iteration moves one pointer toward the other, and pointers never move back. The loop runs at most n - 1 times, and each iteration does constant work.

    Space: O(1). The function uses three integers for the state and one for the current area.

    Edge cases and common mistakes

    • Two lines. [1, 1] gives 1: width 1, height 1.
    • Zero heights. [0, 0] gives 0. A line of height 0 holds nothing, whatever the width.
    • Using the taller line for the height. That overestimates the water, since it would pour over the shorter side.
    • Forgetting the width. The area is the height times the distance between the indices, not times the number of lines.
    • Moving the taller pointer. The width shrinks while the height stays capped by the shorter line, so the scan can lose the best answer.
    • Using left <= right. The pointers would reach the same line, which has width 0 and adds nothing.
    • Wide beats tall sometimes. For [4, 3, 2, 1, 4] the best container is the two 4s at distance 4, area 16, which is bigger than anything involving the middle lines.

    Testing

    • [1, 8, 6, 2, 5, 4, 8, 3, 7] gives 49.
    • [1, 1] gives 1.
    • [0, 0] gives 0.
    • [4, 3, 2, 1, 4] gives 16.
    • [1, 2, 1] gives 2.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free