Solusi Leetcode - Container With Most Water

Mencari container dengan air terbanyak dimulai dengan brute force search ke setiap pasangan. Versi two pointer menghasilkan hasil yang sama dalam waktu O(n) dengan membuang pasangan yang nggak mungkin memperbesar luas.

Batasan luas

Input height berisi garis-garis vertikal. Garis i membentang dari (i, 0) ke (i, height[i]). Untuk dua index left dan right, lebar container adalah right - left, dan tingginya min(height[left], height[right]). Luasnya adalah hasil kali keduanya.

Pendekatan awal saya mengecek setiap kemungkinan pasangan garis:

function maxAreaNaive(height) {
    let maxArea = 0;

    // Check every possible pair
    for (let i = 0; i < height.length - 1; i++) {
        for (let j = i + 1; j < height.length; j++) {
            let width = j - i;
            let currentArea = Math.min(height[i], height[j]) * width;
            maxArea = Math.max(maxArea, currentArea);
        }
    }

    return maxArea;
}

Metode per pasangan ini benar, tapi butuh waktu O(n²). Dengan n sampai 10^5, pengecekan pasangan sebanyak itu terlalu mahal.

Aturan two pointer dan implementasinya

Mulai dari garis pertama dan terakhir, yang memberikan container paling lebar. Kalau height[left] lebih pendek, menggeser right bakal mengurangi lebar, sementara tinggi pembatasnya tetap sama atau malah lebih rendah. Langkah itu nggak mungkin menghasilkan luas yang lebih baik untuk garis kiri yang sekarang. Menggeser left adalah satu-satunya langkah yang mungkin menemukan garis pembatas yang lebih tinggi. Argumen yang sama berlaku kalau garis kanan yang lebih pendek.

function maxArea(height) {
    let maxArea = 0;
    let start = 0;                    // Left pointer
    let end = height.length - 1;      // Right pointer

    while (start < end) {
        let width = end - start;
        // Area is limited by the shorter line
        let currentArea = Math.min(height[start], height[end]) * width;
        maxArea = Math.max(maxArea, currentArea);

        // Move the pointer with the shorter line
        if (height[start] <= height[end]) {
            start++;
        } else {
            end--;
        }
    }

    return maxArea;
}

// Driver Code
function main() {
    let heightsArray = [1, 8, 6, 2, 5, 4, 8, 3, 7];
    console.log("Input heights: ", heightsArray);
    let result = maxArea(heightsArray);
    console.log("Max water that can be contained: ", result);
}

main();

Invariant dan penelusuran

Setiap iterasi menghitung luas terbaik untuk pasangan saat ini, lalu membuang sisi yang membatasi luas itu. Untuk setiap pasangan yang dibuang, lebarnya nggak lebih besar dari lebar saat ini. Tingginya juga nggak lebih tinggi dari garis yang lebih pendek. Jadi, luasnya nggak mungkin melebihi luas yang udah dicek untuk sisi itu.

Untuk [1, 8, 6, 2, 5, 4, 8, 3, 7], tiga evaluasi pertamanya adalah:

• Mulai: left=0 (height=1), right=8 (height=7), area = min(1,7) × 8 = 8
• Geser left (lebih pendek): left=1 (height=8), right=8 (height=7), area = min(8,7) × 7 = 49
• Geser right (lebih pendek): left=1 (height=8), right=7 (height=3), area = min(8,3) × 6 = 18
• Lanjutkan sampai kedua pointer bertemu.

Luas maksimum yang ditemukan adalah 49.

Implementasi Java

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int start = 0;
        int end = height.length - 1;

        while (start < end) {
            int width = end - start;
            maxArea = Math.max(maxArea, Math.min(height[start], height[end]) * width);

            if (height[start] <= height[end]) {
                start++;
            } else {
                end--;
            }
        }

        return maxArea;
    }
}

Kompleksitas dan aturan yang bisa dipakai ulang

Saya nggak menyangka aturan greedy ini udah cukup. Scan-nya butuh waktu O(n) dan memakai extra space O(1).

Pola yang berguna di sini: mulai dari kandidat paling lebar, lalu geser pointer yang membatasi hasil saat ini. Aturan itulah yang bikin soal ini nggak perlu pencarian per pasangan.