Solusi Leetcode - Sum of Three Values

Tiga nested loop bisa menemukan tiga angka yang jumlahnya sama dengan target, tapi butuh waktu O(n³). Array yang udah diurutkan memungkinkan pencarian O(n²) dengan two pointers.

Setelah diurutkan, tetapkan satu angka dan pakai two pointers untuk mencari dua angka lainnya. Perbandingan antara jumlah dan target menentukan pointer mana yang bergerak.

Memahami Soalnya

Diberikan array nums dan sebuah nilai target, tentukan apakah ada tiga angka yang jumlahnya sama dengan target. Index-nya harus berbeda (i ≠ j ≠ k). Tantangannya adalah melakukan ini secara efisien tanpa mengecek semua kemungkinan triplet.

Pendekatan Pertama Saya

Solusi awal saya cukup lugas: cek semua kemungkinan triplet pakai tiga nested loop.

function hasThreeSumNaive(nums, target) {
  const n = nums.length;
  for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
        if (nums[i] + nums[j] + nums[k] === target) {
          return true;
        }
      }
    }
  }
  return false;
}

Tiga loop itu butuh waktu O(n³). Setiap tambahan nilai input menambah jumlah triplet yang harus dicek.

Insight-nya: Sorting + Two Pointers

Pendekatan yang dioptimasi menggabungkan dua teknik:

1. Urutkan array-nya dulu: Ini yang memungkinkan teknik two pointers
2. Tetapkan angka pertama dengan satu loop
3. Pakai two pointers untuk mencari dua angka lainnya

Urutan yang udah terurut bikin pencarian bisa membuang pasangan yang nggak mungkin. Kalau jumlahnya terlalu kecil, nggak ada nilai kanan yang lebih kecil yang bisa menghasilkan target dengan nilai kiri yang sekarang. Pointer kiri maju. Kalau jumlahnya terlalu besar, nggak ada nilai kiri yang lebih besar yang bisa menghasilkan target dengan nilai kanan yang sekarang. Pointer kanan bergeser ke kiri. Nilai array yang sama bisa bikin jumlahnya nggak berubah.

Implementasi two pointer

function hasThreeSum(nums, target) {
  // Sort first - this is key!
  nums.sort((a, b) => a - b);
  const n = nums.length;

  // Fix the first number
  for (let i = 0; i < n - 2; i++) {
    let left = i + 1; // Second number starts after first
    let right = n - 1; // Third number starts at the end

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === target) {
        return true; // Found it!
      } else if (sum < target) {
        left++; // Need a larger sum, move left pointer right
      } else {
        right--; // Sum too large, move right pointer left
      }
    }
  }

  return false; // No triplet found
}

Trace pointer

Untuk nums = [1, 2, 3, 4, 5] dan target = 9, pointer-pointer-nya bergerak seperti ini:

Setelah diurutkan: [1, 2, 3, 4, 5] (di kasus ini udah terurut)

• i = 0 (tetapkan 1), left = 1 (nilai 2), right = 4 (nilai 5): sum = 1+2+5 = 8 < 9
  • Jumlahnya terlalu kecil, geser pointer kiri ke kanan
• i = 0 (tetapkan 1), left = 2 (nilai 3), right = 4 (nilai 5): sum = 1+3+5 = 9 ✓ Ketemu!

Kuncinya, karena array-nya terurut, kita tahu:

• Menggeser pointer kiri ke kanan nggak bisa mengurangi jumlahnya
• Menggeser pointer kanan ke kiri nggak bisa menambah jumlahnya
• Kita bisa membuang banyak kemungkinan tanpa perlu mengeceknya

Kenapa Sorting Membantu

Sorting memungkinkan teknik two pointers karena memberi kita perilaku yang bisa diprediksi:

• Kalau jumlahnya terlalu kecil: Geser pointer kiri ke kanan. Nilai berikutnya lebih besar dari atau sama dengan nilai sebelumnya.
• Kalau jumlahnya terlalu besar: Geser pointer kanan ke kiri. Nilai berikutnya lebih kecil dari atau sama dengan nilai sebelumnya.
• Kita bisa membuang kemungkinan: Kalau nums[i] + nums[left] + nums[right] > target, setiap nilai kanan yang lebih besar juga bikin jumlahnya terlalu besar.

Analisis Kompleksitas

Time Complexity: O(n²)

• Sorting butuh O(n log n)
• Loop luar jalan sebanyak n-2 kali
• Untuk setiap iterasi luar, while loop di dalamnya jalan paling banyak n kali
• Total: O(n log n) + O(n²) = O(n²)

Space Complexity: O(1) untuk scan pointer, ditambah workspace untuk sort

Pointer-pointer itu pakai extra space yang konstan. Pemanggilan nums.sort() bisa mengalokasikan memori tambahan. V8 mendokumentasikan storage sementara di implementasi sorting mereka. Batas O(1) cuma berlaku untuk scan setelah sorting. Fungsi ini juga mengubah urutan array input.

Kesalahan yang Sering Terjadi

Waktu mengimplementasikan ini, hati-hati dengan:

1. Lupa mengurutkan: Teknik two pointers cuma jalan di array yang terurut
2. Off by one error: Pastikan batas loop kamu benar (i < n - 2, left < right)
3. Penanganan duplikat: Kalau soalnya minta triplet yang unik, kamu perlu melewati duplikat
4. Integer overflow: Untuk angka yang sangat besar, jumlahnya bisa overflow

Ringkasan pencarian jumlah

• Sorting memungkinkan two pointers mengurangi satu dimensi dari nested loop
• Tetapkan satu elemen, lalu pakai two pointers untuk nilai-nilai sisanya
• Time complexity membaik dari O(n³) jadi O(n²), dan pola ini berlaku juga untuk soal-soal sum yang mirip

Sorting dan two pointers berguna kalau dipakai bareng ketika soal meminta kombinasi yang mencapai target.