Wawancara Koding: Bagaimana Cara Menemukan Longest Increasing Subsequence?

Masalah dan skenario yang berlaku

Diberikan sebuah array integer nums, kembalikan salah satu subsequence yang naik secara strictly (strictly increasing) terpanjang. Subsequence mempertahankan urutan relatif dari input tetapi tidak harus kontigu. "Strictly increasing" berarti setiap nilai berikutnya harus lebih besar, sehingga nilai yang sama tidak dapat menambah panjang. Jika terdapat beberapa jawaban optimal, kembalikan yang mana saja. Kembalikan array kosong jika input kosong.

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: [2, 3, 7, 18]

Increasing indices: 2 < 4 < 5 < 7
Increasing values:  2 < 3 < 7 < 18
Length: 4

Asumsikan 0 ≤ n ≤ 100,000, nilai integer 32-bit bertanda (signed), dan array input yang tidak boleh diubah. Skala ini mengesampingkan enumerasi seluruh subsequence dan mengesampingkan pemrograman dinamis (DP) kuadratik sebagai solusi akhir. Soal LeetCode meminta panjang dari strictly increasing subsequence dan secara eksplisit memberikan pertanyaan lanjutan dengan target O(n log n). Sebuah artikel persiapan wawancara publik bertanggal April 2026 masih mengajarkan baik DP kuadratik maupun optimasi binary search. Versi ini juga meminta pengembalian subsequence sebenarnya. Sumber-sumber tersebut menetapkan masalah dan nilai persiapannya saat ini; mereka tidak menetapkan frekuensi wawancara atau atribusi perusahaan.

Hal yang dievaluasi pewawancara

Sinyal pertama adalah definisi status (state) yang tepat. Solusi kuadratik harus mendefinisikan dp[i] sebagai panjang terbaik yang harus berakhir di nums[i]. Hanya mengatakan "jawaban untuk i nilai pertama" akan membuang informasi nilai akhir yang diperlukan untuk memutuskan apakah elemen saat ini dapat ditambahkan.

Sinyal kedua adalah menurunkan optimasi dari bottleneck. Memindai setiap j sebelumnya untuk setiap i membutuhkan biaya O(n²). Jawaban yang lebih kuat mengubah statusnya: untuk setiap panjang yang dapat dicapai, simpan hanya nilai akhir terkecil. Nilai akhir (tail) yang lebih kecil setidaknya sama mudahnya untuk diperpanjang. Minimum tails ini strictly increasing, sehingga posisi pembaruan dapat ditemukan dengan binary search.

Sinyal ketiga adalah menangani duplikat dengan benar. Urutan yang strictly increasing memerlukan posisi pertama yang tail-nya lebih besar dari atau sama dengan nilai saat ini: semantik lower-bound. Nilai yang sama menggantikan posisi yang sama dan tidak memperpanjang urutan. Hanya varian non-decreasing yang menggunakan posisi pertama yang strictly greater daripada nilai tersebut.

Sinyal keempat adalah mengetahui bahwa tails itu sendiri bukanlah jawabannya. Setelah [3, 5, 6, 2], nilai tail adalah [2, 5, 6]. Nilai-nilai tersebut meningkat secara nilai, tetapi indeks input asalnya adalah 3, 1, 2, sehingga mereka bukan merupakan subsequence yang valid. Untuk mengembalikan path yang sebenarnya, simpan juga indeks input saat ini untuk setiap panjang tail dan indeks pendahulu (predecessor) untuk setiap elemen.

Sinyal terakhir adalah pembuktian dan validasi. Seorang kandidat harus menjelaskan invarian minimum-tail, mengapa penggantian elemen tidak akan menghilangkan panjang optimal, mengapa tautan pendahulu membentuk path yang valid, dan bagaimana membandingkan input kecil acak dengan oracle O(n²) daripada hanya mengandalkan satu contoh.

Pertanyaan klarifikasi sebelum menjawab

• Strictly increasing atau non-decreasing? Masalah ini adalah strict, sehingga nilai duplikat tidak dapat memperpanjang jawaban. Jika nilai yang sama diizinkan, batas binary search akan berubah.
• Kembalikan panjangnya atau urutan sebenarnya? Masalah ini mengembalikan urutan sebenarnya, jadi memerlukan previous dan indeks tail. Solusi yang hanya mengembalikan panjang dapat mengurangi ruang bantu menjadi O(L), di mana L adalah panjang jawaban.
• Bagaimana cara menyelesaikan seri (ties) antara jawaban optimal? Jawaban mana pun dapat diterima. Persyaratan memilih urutan terkecil secara leksikografis, indeks terkecil, atau pemilihan yang stabil memerlukan aturan dan bukti tambahan.
• Berapa ukuran inputnya? Pada seratus ribu elemen, gunakan O(n log n). Untuk beberapa ratus elemen, DP kuadratik lebih mudah diimplementasikan, dijelaskan, dan diperluas untuk penghitungan (counting).
• Apakah input bisa kosong? Ya; kembalikan []. Ini menentukan apakah rekonstruksi boleh membaca indeks tail akhir.
• Bolehkah input dimodifikasi? Tidak. Pengurutan (sorting) merusak urutan indeks asli dan mengubah masalah.
• Bisakah aritmatika integer mengalami overflow? Algoritma hanya membandingkan dan menyalin nilai tanpa operasi aritmatika padanya, sehingga input 32-bit bertanda tidak akan mengalami overflow karena algoritma.

Kerangka jawaban 30 detik

"Saya menyimpan tail terkecil untuk setiap panjang yang dapat dicapai. Nilai-nilai tail tersebut terurut, jadi untuk setiap nilai saya melakukan binary search untuk mencari tail pertama yang lebih besar dari atau sama dengannya, mengganti posisi tersebut, atau menambahkannya di akhir. Lower bound ini mencegah nilai duplikat memperpanjang urutan yang strict. Array tail mungkin mencampur indeks input yang tidak kompatibel, jadi saya juga menyimpan indeks masing-masing tail dan pendahulu per elemen, lalu merekonstruksi mundur. Satu binary search per elemen menghasilkan waktu O(n log n) dan ruang O(n). Saya menguji array kosong, duplikat, menurun, dan array kecil acak terhadap oracle kuadratik."

Solusi mendalam langkah-demi-langkah

Mulailah dengan baseline yang paling mudah dibuktikan. Misalkan dp[i] adalah panjang dari strictly increasing subsequence terpanjang yang harus berakhir di nums[i]. Setiap jawaban yang lebih panjang dari satu memiliki elemen kedua dari belakang pada suatu j < i dengan nums[j] < nums[i]:

dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i]
If no such j exists, dp[i] = 1
Final length = max(dp[i])

Definisi ini juga membuktikan relasi rekursifnya. Setiap pendahulu yang memenuhi syarat dapat diperpanjang sebesar nums[i], sementara setiap urutan optimal yang berakhir di nums[i] harus bertransisi dari salah satu pendahulu tersebut. Masalahnya adalah setiap i memindai semua posisi sebelumnya, sehingga memakan total waktu O(n²).

Untuk optimasi, pertahankan invarian prefix ini: setelah memproses i elemen pertama, tails[k] adalah nilai akhir terkecil yang mungkin di antara semua strictly increasing subsequence dengan panjang k + 1. Untuk nilai saat ini x, temukan posisi pertama yang memenuhi tails[k] ≥ x:

• Jika tidak ada posisi yang ditemukan, x melebihi setiap tail dan memperpanjang urutan terpanjang sebesar satu.
• Jika posisi k ada, ganti tails[k] dengan x. Panjangnya tidak berubah, tetapi tail yang lebih kecil atau sama tidak dapat mengurangi pilihan ekstensi di masa mendatang.
• Karena tails strictly increasing, posisi tersebut dapat ditemukan dalam waktu O(log L).

Untuk [3, 5, 6, 2], tiga status pertama adalah [3], [3, 5], dan [3, 5, 6]. Nilai terakhir 2 menggantikan posisi pertama, menghasilkan [2, 5, 6]. Panjangnya tetap benar, tetapi 2 muncul setelah 5 dan 6 pada input asli. Ini adalah contoh penyangkal (counterexample) mengapa kita tidak bisa mengembalikan tails secara langsung.

Rekonstruksi membutuhkan dua struktur indeks. tailsIndices[k] menyimpan posisi input yang saat ini merealisasikan minimum tail untuk panjang k + 1. Ketika nums[i] berada pada posisi k, set previous[i] ke tailsIndices[k - 1]. Pendahulu tersebut terjadi sebelum i dan memiliki nilai yang lebih kecil secara strict. Penggantian tail di kemudian hari tidak mengubah tautan pendahulu yang telah ditulis. Rekonstruksi mundur dari tail terpanjang terakhir.

export function longestIncreasingSubsequence(nums: number[]): number[] {
  if (nums.length === 0) return []

  const tails: number[] = []
  const tailsIndices: number[] = []
  const previous = new Array<number>(nums.length).fill(-1)

  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index]
    let left = 0
    let right = tails.length

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2)
      if (tails[middle] < value) left = middle + 1
      else right = middle
    }

    const lengthIndex = left
    if (lengthIndex > 0) {
      previous[index] = tailsIndices[lengthIndex - 1]
    }

    if (lengthIndex === tails.length) {
      tails.push(value)
      tailsIndices.push(index)
    } else {
      tails[lengthIndex] = value
      tailsIndices[lengthIndex] = index
    }
  }

  const result = new Array<number>(tails.length)
  let index = tailsIndices[tails.length - 1]

  for (
    let resultIndex = result.length - 1;
    resultIndex >= 0;
    resultIndex -= 1
  ) {
    result[resultIndex] = nums[index]
    index = previous[index]
  }

  return result
}

Kebenaran algoritma terdiri dari tiga bagian. Pertama, tails tetap strictly increasing: menghapus item terakhir dari urutan naik yang lebih panjang menghasilkan urutan yang lebih pendek dengan tail yang lebih kecil. Kedua, penggantian melalui binary search mempertahankan tail terkecil yang dapat direalisasikan untuk setiap panjang; ini meningkatkan potensi ekstensi tanpa mengarang urutan yang lebih panjang secara keliru. Ketiga, setiap tailsIndices[k] merealisasikan rantai sepanjang k + 1, dengan indeks pendahulu dan nilai yang strictly increasing. Oleh karena itu tails.length tidak dapat melebihi nilai optimal yang sebenarnya, dan memindai LIS nyata mana pun memaksa struktur untuk mencapai setidaknya panjang tersebut. Rantai pendahulu yang direkonstruksi adalah jawaban optimal yang valid.

Setiap elemen melakukan satu binary search pada paling banyak L tail, menghasilkan waktu O(n log L) dan batas atas konvensional O(n log n). Ketiga array menggunakan ruang O(n); output itu sendiri menggunakan O(L). Algoritma tidak mengurutkan input maupun bergantung pada rentang numerik.

Pengujian harus memeriksa panjang, sifat strictly increasing, dan urutan indeks input:

const cases: Array<[number[], number]> = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],
  [[5, 4, 3, 2, 1], 1],
  [[], 0],
]

for (const [nums, expectedLength] of cases) {
  const result = longestIncreasingSubsequence(nums)
  if (result.length !== expectedLength) throw new Error("wrong length")
  for (let i = 1; i < result.length; i += 1) {
    if (result[i - 1] >= result[i]) throw new Error("not increasing")
  }
}

Pemeriksaan yang lebih kuat menghasilkan array acak dengan panjang paling banyak 12 dan membandingkan panjang hasil yang dioptimalkan dengan oracle DP O(n²). Pemindaian linier melalui input juga harus memverifikasi bahwa nilai yang dikembalikan muncul secara berurutan. Bersama-sama, pemeriksaan ini mengungkap bug batas duplikat, kondisi binary search yang salah, dan pendahulu yang rusak.

Contoh jawaban berkualitas tinggi

"Pertama-tama saya akan mengonfirmasi bahwa urutannya bersifat strict dan saya harus mengembalikan urutan yang sebenarnya. Solusi kuadratik mendefinisikan dp[i] sebagai panjang terbaik yang berakhir di nums[i] dan memeriksa setiap pendahulu yang lebih kecil. Untuk menghilangkan pemindaian mundur tersebut, saya menyimpan tail terkecil yang mungkin untuk setiap panjang.

Untuk nilai x, saya mencari tail pertama yang lebih besar dari atau sama dengan x. Jika tidak ada, x memperpanjang urutan terpanjang saat ini. Jika ada, mengganti tail tersebut dengan x memberikan nilai yang setidaknya sama mudahnya untuk diperpanjang pada panjang yang sama. Sifat strictly increasing memerlukan posisi lower-bound ini, sehingga elemen duplikat menggantikan nilai alih-alih memperpanjang panjang urutan.

Nilai-nilai tail merangkum akhiran terbaik untuk setiap panjang; mereka tidak harus berasal dari indeks input yang kompatibel. Untuk mengembalikan jawaban nyata, tailsIndices[k] mencatat indeks tail saat ini untuk panjang k + 1. Ketika suatu elemen menempati posisi k, pendahulunya adalah tailsIndices[k - 1]. Setelah pemindaian selesai, saya menelusuri pendahulu dari tail terpanjang dan mengisi output secara mundur.

Invariannya adalah bahwa setiap tail adalah tail terkecil yang dapat direalisasikan untuk panjangnya, dan setiap indeks tail memiliki rantai pendahulu yang nyata. Penggantian tidak pernah menghapus panjang yang ada dan hanya meningkatkan kemungkinan ekstensi di masa mendatang. Sebaliknya, memindai setiap elemen dari subsequence naik nyata mana pun memaksa struktur untuk mencapai setidaknya panjang tersebut, sehingga panjang akhirnya optimal. Satu binary search per elemen membutuhkan waktu O(n log n), serta array indeks dan pendahulu menggunakan ruang O(n). Saya akan menguji input kosong, duplikat, naik, dan turun, lalu membandingkan array kecil acak dengan oracle kuadratik."

Kesalahan umum

• Menganggap subsequence sebagai subarray kontigu → Sliding window tidak dapat melewati elemen → Definisikan jawaban berdasarkan indeks input yang meningkat.
• Mengurutkan sebelum menyelesaikan → Pengurutan merusak urutan relatif asli → Proses nilai sesuai urutan input.
• Mendefinisikan dp[i] sebagai optimum prefix dan bertransisi secara langsung → Tail dari nilai optimum mungkin tidak dapat menerima nilai saat ini → Wajibkan status berakhir di i.
• Mencari tail pertama yang strictly greater daripada nilai pada varian strict → Duplikat secara keliru memperpanjang panjang → Cari tail pertama yang lebih besar dari atau sama dengan nilai tersebut.
• Mengembalikan tails secara langsung → Nilai tail dapat berasal dari indeks input yang menurun → Rekonstruksi menggunakan indeks tail dan tautan pendahulu.
• Menulis ulang pendahulu lama setelah penggantian tail → Path yang sebelumnya valid menjadi rusak → Jaga agar setiap pendahulu bersifat immutable setelah ditetapkan.
• Hanya membuktikan bahwa tail terurut → Keterurutan saja tidak membuktikan panjang optimal → Buktikan invarian minimum realizable tail dan kedua batas panjang.
• Menyebut binary search ditambah penyisipan array sebagai O(log n) → Penyisipan di tengah menggeser elemen → Hanya ganti di tempat (in place) atau tambahkan di akhir.
• Hanya menjalankan contoh klasik → Bug duplikat dan pendahulu tetap tersembunyi → Gunakan pengujian oracle untuk semua nilai sama, menurun, kosong, dan acak.
• Mengklaim frekuensi tinggi di perusahaan tertentu → Halaman masalah publik tidak membuktikan frekuensi atau atribusi → Sebutkan hanya masalah yang terverifikasi dan nilai algoritmanya.

Pertanyaan lanjutan dan tanggapan

Pertanyaan Lanjutan 1: Apa yang berubah untuk longest non-decreasing subsequence?

Nilai yang sama sekarang boleh memperpanjang urutan. Ubah batas pencarian menjadi posisi pertama yang strictly greater daripada value, yang merupakan titik penyisipan kanan (right insertion point). Pendahulu, rekonstruksi, dan kompleksitas tetap sama. Hanya mengubah perbandingan akhir tanpa mengubah batas binary search akan gagal pada kasus duplikat.

Pertanyaan Lanjutan 2: Bisakah jawaban yang hanya meminta panjang menggunakan lebih sedikit ruang?

Ya. Hapus tailsIndices dan previous, lalu pertahankan hanya L nilai minimum tail untuk ruang O(L). Waktu tetap O(n log L). Mengembalikan urutan sebenarnya memang membutuhkan output O(L), sedangkan rekonstruksi satu-lintasan ini menggunakan informasi pendahulu untuk setiap posisi input.

Pertanyaan Lanjutan 3: Bagaimana cara menghitung jumlah longest increasing subsequence?

Minimum tails menggabungkan beberapa path dengan panjang yang sama, sehingga tidak dapat memulihkan hitungan secara langsung. Solusi sederhana mempertahankan length[i] dan count[i]: salin hitungan pendahulu ketika path yang lebih panjang ditemukan dan tambahkan hitungan ketika path dengan panjang yang sama ditemukan, dengan waktu O(n²). Untuk input yang lebih besar, koordinat nilai dapat dikompresi (coordinate compression) dan menggunakan Fenwick tree atau segment tree yang menyimpan pasangan panjang-maksimum-dan-hitungan, dengan aturan penggabungan yang cermat untuk menghindari penghitungan ganda.

Pertanyaan Lanjutan 4: Bagaimana jika nilai datang dalam aliran data append-only?

Panjang LIS saat ini bersifat online: lakukan binary search pada tails untuk setiap nilai yang tiba dalam waktu O(log L). Pertahankan indeks dan pendahulu jika urutan sebenarnya harus tersedia. Jika nilai lama dapat dihapus, minimum tail mungkin bergantung pada data yang dihapus; algoritma ini tidak dapat membatalkan status tersebut secara lokal, sehingga diperlukan struktur dinamis atau dekomposisi offline.

Pertanyaan Lanjutan 5: Bagaimana jika setiap elemen memiliki bobot dan tujuannya adalah total bobot maksimum?

Minimum tail tidak lagi dapat merangkum status karena rentang tail yang sama dapat membawa akumulasi bobot yang berbeda. Lakukan kompresi koordinat pada nilai-nilai tersebut, lakukan query pada Fenwick tree atau segment tree untuk mencari bobot terbaik di antara nilai-nilai yang lebih kecil, tambahkan bobot saat ini, dan perbarui koordinat saat ini. Varian strict dan non-decreasing tetap menggunakan batas query yang berbeda. Waktunya adalah O(n log n).

Pertanyaan Lanjutan 6: Apakah kode ini mengembalikan jawaban optimal yang terkecil secara leksikografis?

Kode ini tidak menjamin hal tersebut. Aturan penggantian meminimalkan nilai tail individual tetapi tidak mendefinisikan urutan stabil di antara seluruh path optimal yang lengkap. Salah satu pendekatannya adalah menghitung seberapa banyak prefix atau suffix optimal yang dapat didukung oleh setiap indeks, lalu secara greedy memilih nilai yang masih dapat menyelesaikan jawaban dengan panjang optimal. Urutan nilai terkecil dan urutan indeks terkecil adalah persyaratan yang berbeda, jadi klarifikasi terlebih dahulu urutan leksikografis mana yang dimaksud.