Dasar Array dan Operasi In-Place
Tinjau pengindeksan dan perubahan data, serta jebakan umum array dalam wawancara seperti kesalahan batas satu posisi dan mengubah list saat melakukan iterasi.
Dasar Array dan Operasi In-Place adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Larik sebagai Memori Kontigu
Di balik layar, daftar Python didukung oleh larik dinamis — blok memori kontigu tempat elemen disimpan pada alamat yang berurutan. Tata letak ini memberikan akses acak O(1) berdasarkan indeks: Python menghitung address = base + index × element_size secara instan. Penyisipan atau penghapusan di bagian tengah memerlukan penggeseran semua elemen setelahnya, dengan biaya O(n). Asimetri inilah yang menjadi sumber sebagian besar pembahasan pertukaran penggunaan larik dalam wawancara.
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]Selisih Satu: Kesalahan Larik Klasik
Kesalahan selisih satu adalah sumber jawaban yang salah paling sering dalam masalah larik. Pengindeksan Python yang dimulai dari 0 berarti indeks valid terakhir adalah len(arr) - 1. Saat menulis perulangan, tentukan apakah Anda memerlukan < atau <= dengan memeriksa kondisi batas menggunakan input valid terkecil (n=1 atau n=2). Selalu telusuri batas Anda dengan contoh konkret sebelum mengirimkan jawaban.
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]Pembalikan di Tempat dengan Dua Penunjuk
Membalik larik di tempat menggunakan dua penunjuk yang dimulai dari ujung berlawanan dan saling bertukar ke arah tengah hingga bertemu. Proses ini memerlukan ruang tambahan O(1) dan waktu O(n). Kondisi left < right (lebih kecil secara ketat) memastikan kebenaran untuk panjang genap maupun ganjil — pada jumlah elemen ganjil, elemen tengah otomatis tetap di tempatnya.
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchangedMemutar Larik di Tempat
Memutar larik ke kanan sebanyak k posisi dapat dilakukan di tempat dengan membalik tiga segmen: balik seluruh larik, lalu balik k elemen pertama, kemudian balik n-k elemen yang tersisa. Cara ini mencapai waktu O(n) dan ruang O(1) — jauh lebih baik daripada pendekatan dengan ruang O(n) yang menggunakan pengirisan dan penggabungan. Selalu kurangi k dengan modulo n untuk menangani k ≥ n.
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]Menghapus Elemen di Tempat
Menghapus duplikat atau nilai target di tempat menggunakan penunjuk tulis yang melacak posisi tempat elemen valid berikutnya harus ditulis. Penunjuk baca memindai ke depan; saat menemukan elemen yang valid, penunjuk tersebut menyalinnya ke posisi tulis dan memajukan kedua penunjuk. Ini adalah pola inti untuk masalah LeetCode seperti “menghapus elemen”, “menghapus duplikat dari larik terurut”, dan “memindahkan nol”.
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]Memindahkan Nol: Penunjuk Baca-Tulis
Pindahkan semua angka nol ke akhir larik sambil mempertahankan urutan elemen yang bukan nol. Pendekatan penunjuk baca-tulis menempatkan setiap elemen bukan nol pada posisi penulisan, lalu mengisi bagian akhir dengan angka nol. Pendekatan alternatif menukar angka nol ke arah belakang, sehingga urutan tetap terjaga tanpa lintasan pengisian kedua. Keduanya membutuhkan waktu O(n) dan ruang O(1).
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]Menguadratkan dan Mengurutkan di Tempat
Diberikan larik bilangan bulat yang terurut dan mungkin berisi bilangan negatif, kembalikan larik berisi kuadratnya dalam urutan terurut. Pendekatan naif menguadratkan elemen lalu mengurutkannya: O(n log n). Pendekatan dua penunjuk yang optimal memanfaatkan fakta bahwa kuadrat terbesar berasal dari salah satu ujung masukan yang terurut: bandingkan nilai mutlak elemen paling kiri dan paling kanan, lalu isi hasil dari kanan ke kiri dalam waktu O(n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Menemukan Elemen Pembagi dan Mempartisi
Masalah bendera nasional Belanda mempartisi larik menjadi tiga bagian (lebih kecil dari, sama dengan, dan lebih besar dari elemen pembagi) langsung di tempat menggunakan tiga penunjuk. Ini adalah sublangkah utama dalam pengurutan cepat dan solusi untuk LeetCode 'sort warna'. Mempertahankan invarian bahwa elemen sebelum penunjuk batas bawah bernilai < elemen pembagi dan elemen setelah penunjuk batas atas bernilai > elemen pembagi menjadi penggerak algoritme ini.
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]Memodifikasi Elemen Larik Saat Melakukan Iterasi
Anda dapat dengan aman memodifikasi nilai elemen (misalnya, mengalikannya dengan -1 untuk menandai elemen yang telah dikunjungi) saat melakukan iterasi, tetapi jangan pernah mengubah panjang daftar selama perulangan. Trik pengodean yang aman: untuk sementara menyandikan dua nilai dalam satu bilangan bulat (misalnya, menggunakan bit tanda) guna menyimulasikan satu nilai logis tambahan per elemen tanpa mengalokasikan ruang tambahan. Teknik ini muncul dalam soal seperti 'menemukan semua angka yang hilang dalam sebuah larik'.
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra spaceDaftar Periksa Pola Wawancara tentang Larik
Sebelum menulis kode untuk soal larik apa pun, gunakan daftar periksa mental ini:
- Apakah larik sudah terurut? (memungkinkan penggunaan dua penunjuk dan pencarian biner)
- Apakah elemen-elemennya berada dalam batas tertentu (misalnya, 1..n)? (memungkinkan trik berbasis indeks)
- Apakah harus dilakukan langsung di tempat? (penunjuk baca-tulis atau pertukaran)
- Apakah saya memerlukan semua pasangan atau hanya satu? (menentukan apakah perulangan bertingkat dapat diterima)
- Kasus tepi: larik kosong, satu elemen, semua nilai sama
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0Algoritme Kadane: Sublarik Maksimum
Algoritme Kadane menemukan sublarik berurutan dengan jumlah maksimum dalam waktu O(n) dan ruang O(1). Pada setiap langkah, tentukan apakah akan memperpanjang sublarik saat ini atau memulai sublarik baru: current = max(num, current + num). Jika current + num lebih kecil daripada num saja, sublarik saat ini menurunkan hasil sehingga kita memulainya kembali. Lacak maksimum global selama proses berlangsung.
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari bahwa: larik menyediakan akses acak O(1), tetapi penyisipan dan penghapusan di bagian tengah membutuhkan O(n) — memahami ketidaksimetrian ini membantu menentukan pilihan algoritme, pola penunjuk baca-tulis menghapus elemen atau memindahkan nilai langsung di tempat dalam waktu O(n) dengan ruang O(1), dan pengodean bit tanda serta trik menggunakan indeks sebagai penanda memungkinkan solusi dengan ruang O(1) untuk soal yang jika tidak demikian memerlukan larik tambahan. Selanjutnya kita akan membahas jumlah prefiks dan total berjalan.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Dasar Array dan Operasi In-Place” gratis?
Ya — teks lengkap “Dasar Array dan Operasi In-Place” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Dasar Array dan Operasi In-Place”?
Tinjau pengindeksan dan perubahan data, serta jebakan umum array dalam wawancara seperti kesalahan batas satu posisi dan mengubah list saat melakukan iterasi. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Dasar Array dan Operasi In-Place” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Dasar Array dan Operasi In-Place
- Jumlah Awalan dan Total Berjalan
- Dua Pointer: Ujung Berlawanan
- Dua Pointer: Lambat dan Cepat