配列の基礎とin-place操作
インデックス、変更操作、off-by-oneエラーや反復中のリスト変更など、面接で頻出する配列の落とし穴を復習します。
「配列の基礎とin-place操作」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
連続したメモリとしての配列
内部では、Pythonのリストは動的配列によって支えられています。これは、要素が連続したアドレスに格納される、連続したメモリ領域です。この配置により、インデックスによるランダムアクセスをO(1)で実行できます。Pythonはaddress = base + index × element_sizeを瞬時に計算します。一方、中央への挿入や削除では、それ以降のすべての要素を移動する必要があるため、O(n)のコストがかかります。この非対称性が、配列に関する面接でトレードオフが議論される主な理由です。
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]オフバイワン: 配列でよくあるバグ
オフバイワンエラーは、配列問題で誤答を生む最も一般的な原因です。Pythonの0始まりのインデックスでは、最後の有効なインデックスはlen(arr) - 1です。ループを書くときは、最小の有効な入力（n=1またはn=2）で境界条件を確認し、<と<=のどちらが必要かを判断してください。提出する前に、具体例を使って境界の動作を必ず追跡しましょう。
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)]2つのポインターによるインプレース反転
配列をインプレースで反転するには、両端に2つのポインターを置き、中央に向かって交換していきます。必要な追加領域はO(1)、時間計算量はO(n)です。条件にleft < right（厳密な小なり）を使うことで、要素数が偶数の場合も奇数の場合も正しく処理できます。要素数が奇数の場合は、中央の要素が自動的にその場に残ります。
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 unchanged配列をインプレースで回転する
配列を右にk個分回転させるには、3つの区間を反転することでインプレースに処理できます。まず配列全体を反転し、次に最初のk個の要素を反転し、最後に残りのn-k個の要素を反転します。これにより、スライスと連結を使うO(n)の空間の方法よりも効率よく、時間O(n)、空間O(1)を実現できます。k ≥ nの場合にも対応できるよう、必ず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]要素をインプレースで削除する
重複や対象の値をインプレースで削除するには、次に有効な要素を書き込む位置を追跡する書き込みポインターを使います。読み取りポインターが前方に走査し、有効な要素を見つけたら書き込み位置にコピーして、両方のポインターを進めます。これは、'remove element'、'remove duplicates from sorted array'、'move zeroes'のようなLeetCodeの問題で使われる基本パターンです。
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]ゼロの移動：読み書きポインター
配列内のすべての 0 を末尾へ移動し、0 以外の要素の順序を維持します。読み書きポインター方式では、各 0 以外の要素を書き込み位置に配置してから、末尾を 0 で埋めます。別の方法では、0 を後方へ交換していくことで、2 回目の埋める処理を行わずに順序を維持します。どちらも時間計算量は O(n)、空間計算量は 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]二乗してインプレースでソート
負の値を含む可能性がある整数のソート済み配列が与えられたとき、各要素を二乗した値をソート済みの配列として返します。単純な方法では、二乗してからソートするため、計算量は O(n log n) です。最適な 2 ポインター方式では、入力配列の両端から最大の二乗値が得られるという性質を利用します。左端と右端の要素の絶対値を比較し、結果を右から左へ埋めることで、時間計算量 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]ピボットの特定と分割
オランダ国旗問題では、3 つのポインターを使って、配列をピボットより小さい要素、等しい要素、大きい要素の 3 つの区間にインプレースで分割します。これはクイックソートにおける重要なサブステップであり、LeetCode の「sort colors」の解法でもあります。low ポインターより前の要素は < pivot、high ポインターより後の要素は > pivot という不変条件を維持することが、アルゴリズムを前進させます。
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]反復処理中の配列要素の変更
反復処理中に、要素の値を変更すること（たとえば、訪問済みの印として -1 を掛けること）は安全に行えます。ただし、for ループの実行中にリストの長さを変更してはいけません。安全な符号化の工夫として、1 つの整数に一時的に 2 つの値を符号化する（たとえば、符号ビットを使う）方法があります。これにより、追加の領域を確保せずに、各要素にブール値を 1 つ追加したように扱えます。この方法は、「配列から消えたすべての数を見つける」といった問題で使われます。
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 space配列問題の面接パターンチェックリスト
配列問題のコードを書く前に、次のチェックリストを頭の中で確認します。
- 配列はソート済みですか？（2 ポインターや二分探索が使えます）
- 要素の値域は限定されていますか？（例：1..n）（インデックスを利用した工夫が使えます）
- インプレースでの処理が必要ですか？（読み書きポインターまたは交換を使います）
- すべてのペアが必要ですか、それとも 1 つだけでよいですか？（入れ子のループが許容されるかどうかに影響します）
- エッジケース：空の配列、要素が 1 つだけの配列、すべて同じ値
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])) # 0Kadane's Algorithm：最大部分配列
Kadane's algorithmは、合計が最大になる連続した部分配列を、時間計算量 O(n)、空間計算量 O(1) で見つけます。各ステップで、現在の部分配列を拡張するか、新しい部分配列を開始するかを判断します。current = max(num, current + num)。current + num が num 単独より小さい場合、現在の部分配列は合計を下げているため、そこから新しく始めます。処理全体を通して最大値を記録します。
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)理解度チェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の内容を理解できているか確認します。
レッスンのまとめ
このレッスンでは、配列は O(1) のランダムアクセスを提供する一方、中央での挿入と削除には O(n) かかるため、この非対称性を知ることがアルゴリズムの選択につながること、読み書きポインターのパターンにより、O(1) の空間で O(n) の時間内に要素の削除や値の移動をインプレースで行えること、そして符号ビットによる符号化やインデックスをマークとして使う工夫により、補助配列が必要になる問題を O(1) の空間で解けることを学びました。次は累積和と累計値について学びます。
よくある質問
「配列の基礎とin-place操作」レッスンは無料ですか？
はい。「配列の基礎とin-place操作」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「配列の基礎とin-place操作」で何を学びますか？
インデックス、変更操作、off-by-oneエラーや反復中のリスト変更など、面接で頻出する配列の落とし穴を復習します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「配列の基礎とin-place操作」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 配列の基礎とin-place操作
- 累積和とランニングトータル
- Two Pointers：両端から近づける
- Two Pointers：遅いポインターと速いポインター