Wawancara Koding: Menghitung Permutasi Berikutnya Secara In-Place

Apa yang dievaluasi oleh pewawancara

Diberikan sebuah array integer yang mungkin mengandung duplikat, ubah array tersebut secara in-place menjadi permutasi leksikografis berikutnya yang lebih besar secara ketat; jika urutan saat ini sudah maksimal, hasilkan permutasi menaik terkecil.

Batasan dan kondisi batas

Gunakan ruang ekstra O(1) dan hanya gunakan operasi swap atau reverse.
Nilai duplikat bukanlah entitas yang berbeda, tetapi perbandingannya bersifat numerik.
Array kosong dan array dengan satu elemen tetap tidak berubah.
Hasilnya harus berupa permutasi leksikografis yang bersebelahan secara global, bukan pertukaran lokal sembarangan.

Menemukan pivot paling kanan

Pindai dari arah kanan untuk mencari indeks pertama i di mana nilai di sebelah kiri lebih kecil secara ketat daripada nilai di sebelah kanan. Sufiks tersebut sudah dalam keadaan tidak menaik (non-increasing). Jika tidak ada pivot, seluruh array sudah berada dalam kondisi maksimal; balikkan array untuk mendapatkan permutasi minimum.

Menukar dan meminimalkan sufiks

Setelah menemukan pivot, pindai dari arah kanan untuk mencari nilai pertama yang lebih besar dari nums[i]. Karena sufiks tidak menaik, kandidat pertama tersebut adalah nilai lebih besar yang paling kecil yang memungkinkan. Tukar nilai tersebut dengan pivot, lalu balikkan sufiks setelah i agar menjadi menaik (ascending).

Kerangka jawaban 30 detik

“Pindai dari arah kanan untuk mencari pivot pertama yang menaik i. Jika tidak ada, balikkan array menurun yang maksimal tersebut. Jika ada, temukan nilai paling kanan yang lebih besar dari nums[i], tukar keduanya, dan balikkan sufiksnya. Sufiks awalnya terurut ke arah berlawanan, sehingga langkah ini menghasilkan peningkatan terkecil yang memungkinkan dalam waktu O(n) dan ruang O(1).”

Pertanyaan klarifikasi sebelum menjawab

Apakah mutasi harus dilakukan secara in-place? Ruang ekstra memungkinkan pengurutan salinan array, sedangkan in-place memerlukan pembalikan (reversal).
Apakah urutan leksikografis berbasis numerik atau string? Nilai negatif dan multi-digit memiliki perlakuan berbeda.
Apakah nilai boleh berulang? Duplikat memerlukan perbandingan ketat baik untuk pivot maupun kandidat pertukaran.

Pembahasan mendalam langkah demi langkah

Untuk [1,2,3], pivot pada 1 ditukar dengan nilai sufiks lebih besar yang paling kecil 2, menyisakan [2,1,3] setelah pembalikan sufiks. Untuk [3,2,1], tidak ada pivot yang ditemukan, sehingga pembalikan menghasilkan [1,2,3].

text

i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1
if i >= 0:
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
    swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)

Gunakan “lebih besar dari atau sama dengan” saat melewati kandidat pivot dan “lebih kecil dari atau sama dengan” saat melewati kandidat pertukaran untuk memastikan peningkatan yang ketat. Lakukan pembalikan alih-alih pengurutan karena sufiks sudah terurut, sehingga pembalikan tetap linear dan in-place.

Model jawaban berkualitas tinggi

“Permutasi berikutnya mengubah posisi paling kanan yang memungkinkan dan membuat semua elemen setelahnya menjadi sekecil mungkin. Saya menemukan pivot paling kanan di mana nilai kiri lebih kecil secara ketat dari nilai kanan, menukarnya dengan nilai paling kanan yang lebih besar darinya, dan membalikkan sufiksnya. Tidak adanya pivot berarti array sudah maksimal, sehingga saya membalikkan seluruh array. Pemindaian dan pembalikan bernilai O(n) dan algoritma ini menggunakan variabel tambahan yang konstan.”

Kesalahan umum

Mencari pivot dari kiri sehingga mengubah posisi tingkat yang lebih tinggi.
Berhenti setelah penukaran tanpa meminimalkan sufiks.
Menggunakan 'lebih besar atau sama dengan' untuk kandidat pertukaran, sehingga elemen duplikat gagal meningkatkan urutan secara ketat.
Memanggil fungsi pengurutan umum pada sufiks dan melanggar batasan in-place.
Mengembalikan array yang menurun tanpa perubahan padahal seharusnya kembali ke urutan minimum.

Gejala kegagalan dan perbaikannya

Jika [1,3,2] menjadi [3,1,2], pivot terlalu jauh ke kiri; hasil yang benar adalah [2,1,3]. Jika [1,1,5] menukar nilai yang sama, batas perbandingan ketat salah.

Implementasi produksi

Terima urutan random-access yang dapat dimutasi dan balikkan dengan dua pointer. Jika perbandingan dapat meluap (overflow) atau urutan bahasa berbeda, tentukan pembanding (comparator) dan kebijakan input tidak valid pada batas antarmuka.

Daftar periksa verifikasi

Uji array kosong, satu elemen, menaik, menurun, duplikat, pivot di akhir, dan beberapa nilai optimum yang sama. Untuk array kecil, hasilkan semua permutasi yang berbeda, urutkan secara leksikografis, dan verifikasi bahwa fungsi mengembalikan item berikutnya atau kembali ke item pertama.

Pertanyaan lanjutan dan jawaban

Mengapa pivot harus merupakan yang paling kanan?

Pivot yang lebih ke kanan mengubah posisi dengan tingkat yang lebih rendah. Memilih nilai lebih besar terkecil yang memungkinkan dan meminimalkan sufiksnya menghasilkan permutasi yang bersebelahan alih-alih melompati urutan yang valid.

Mengapa sufiks dapat dibalik secara langsung?

Pemindaian pivot dari kanan ke kiri membuktikan bahwa sufiks tersebut tidak menaik. Setelah pertukaran, membalikkannya akan memulihkan urutan menaik terkecil tanpa memerlukan pengurutan umum.

Bagaimana dengan permutasi ke-k berikutnya?

Mengulangi operasi ini membutuhkan biaya O(k n). Untuk k yang besar, pendekatan rank/unrank atau penghitungan dapat langsung melompat, tetapi memerlukan penghitungan kombinatorial dan penanganan duplikat.

Rubrik penilaian

Pivot: menemukan kenaikan ketat paling kanan.
Swap: memilih nilai pertama yang lebih besar secara ketat dari kanan.
Sufiks: membalikkannya menjadi urutan menaik terkecil.
Batasan: mencakup array menurun, duplikat, kosong, dan satu elemen.
Kompleksitas: menghasilkan waktu O(n) dan ruang ekstra O(1).

Pemeriksaan kepatuhan

Pastikan bahwa ketiga langkah, contoh kasus batas, dan klaim kompleksitas tetap konsisten.

Daftar periksa jawaban wawancara

Jelaskan perubahan terkecil di sisi kanan, tulis logika pivot, swap, dan reverse, gunakan contoh duplikat untuk perbandingan ketat, lalu berikan kompleksitas dan pengujian permutasi kecil secara menyeluruh.

Kesimpulan utama

Permutasi berikutnya ditemukan secara in-place melalui pivot paling kanan, pertukaran nilai lebih besar terkecil yang memungkinkan, dan pembalikan sufiks dalam waktu linear.