Two Pointer pada Array Terurut

Teknik dua penunjuk memindai larik dengan dua indeks, bukan dengan perulangan bersarang, sehingga banyak gagasan O(n^2) berubah menjadi satu lintasan O(n) yang rapi. 🎯

Versi klasiknya membutuhkan larik yang terurut. Urutan membantu Anda bernalar: bergerak ke kanan memperbesar nilai, sedangkan bergerak ke kiri memperkecilnya, sehingga setiap langkah merupakan keputusan nyata.

Mulailah satu penunjuk di ujung kiri dan satu lagi di ujung kanan. Keduanya saling berhadapan dan perlahan akan mempersempit jarak di antara mereka.

Pada setiap langkah, Anda menggerakkan tepat satu penunjuk ke arah dalam. Urutan larik memberi tahu sisi mana yang perlu digeser agar Anda semakin dekat dengan tujuan.

Teruskan perulangan selama left < right. Saat keduanya bertemu atau saling melewati, semua pasangan yang berguna sudah diperiksa dan Anda dapat berhenti.

Perhatikan a[left] + a[right] sebagai calon hasil saat ini. Membandingkannya dengan sasaran memberi tahu apakah Anda memerlukan nilai yang lebih besar atau lebih kecil berikutnya.

Jika jumlahnya lebih kecil daripada sasaran, Anda memerlukan nilai yang lebih besar. Gerakkan penunjuk kiri ke kanan menuju nilai-nilai yang lebih besar karena larik terurut secara menaik.

Jika jumlahnya lebih besar daripada sasaran, Anda memerlukan nilai yang lebih kecil. Gerakkan penunjuk kanan ke kiri menuju nilai-nilai yang lebih kecil untuk menurunkan jumlah keseluruhan.

Setiap pergerakan menyingkirkan seluruh kelompok pasangan yang tidak perlu Anda uji. Itulah sebabnya pemindaian ini bersifat linear, bukan kuadratik.

Anda hanya membuang pasangan yang tidak mungkin cocok, sehingga jawaban yang benar tidak pernah terlewat. Keamanan inilah yang membuat dua penunjuk dapat diandalkan dalam kontes.

Gagasan yang sama mendukung berbagai variasi: membalik urutan di tempat, mempartisi, dan menggabungkan. Setelah menguasai penunjuk yang saling bertemu, semua teknik ini akan terasa familier.

Dua penunjuk menyapu larik terurut dari kedua ujung, dengan salah satunya bergerak ke dalam pada setiap langkah selama left < right. Linear, benar, dan menjadi dasar bagi banyak trik. 🚀