LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Container With Most Water

Geser dua pointer saling mendekat untuk mencari luas container terbesar dalam waktu linear.

Di artikel ini 5 bagian

Garis yang lebih pendek membatasi air yang bisa ditampung container. Dari sini kita bisa melewati beberapa pasangan: pertahankan garis yang lebih tinggi, lalu geser sisi yang lebih pendek ke dalam.

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.

Baseline ini mengecek setiap pasangan garis:

javascript
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.

javascript
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

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

Setiap pointer bergerak ke dalam paling banyak n kali. Scan ini butuh O(n) waktu dan O(1) extra space.

Garis yang lebih pendek itulah yang dilepas. Mempertahankannya sambil mengurangi lebar nggak bisa memperbesar luas, meskipun garis di sisi satunya lebih tinggi.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan