Two-Pointer Algorithm

Remove Duplicates from Sorted Array II

O(n) Time Complexity

アルゴリズム概要

ソート済み配列から重複要素を除去し、各要素を最大2回まで保持するTwo-Pointerアルゴリズムです。

核心アイデア

1
Read Pointer: 配列を順次スキャン
2
Write Pointer: 有効な要素の書き込み位置
3
比較ロジック: nums[read] != nums[write-2] で3回目を検出

実装コード

solution.py 
from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        Remove duplicates from sorted array such that each unique element
        appears at most twice. Modify nums in-place and return the new length.

        Args:
            nums (List[int]): Sorted integer array

        Returns:
            int: The length of modified array with each element appearing at most twice.
        """
        n: int = len(nums)
        if n <= 2:
            return n

        write: int = 2  # 最初の2要素は必ず残せる
        for read in range(2, n):
            if nums[read] != nums[write - 2]:
                nums[write] = nums[read]
                write += 1

        return write

ステップバイステップ解説

処理フロー

1
初期化
配列長が2以下なら全要素保持、そうでなければwrite=2に設定
2
メインループ
read=2から配列末尾まで順次処理
3
重複チェック
nums[read] != nums[write-2] で3個目かどうか判定
4
要素配置
条件を満たす場合のみnums[write]に要素をコピーしwriteを進める

インタラクティブデモ

Current Step: 初期化

Read: - | Write: -

Action: 例を選択してください

計算量解析

O(n)

時間計算量

配列を一回だけスキャンするため線形時間

O(1)

空間計算量

追加の配列を使わずポインタ変数のみ

なぜ効率的なのか？

✓
In-place処理: 元の配列を直接変更するため追加メモリ不要
✓
単一パス: 配列を一度だけ走査するため最適な時間効率
✓
ソート済み前提: 同じ要素が隣接するため効率的な重複検出が可能

重要なポイント

核心ロジックの理解

核心比較文 
if nums[read] != nums[write - 2]:

なぜ write-2 を見るのか？

💡
結果領域の管理
write-2は結果領域の「2つ前の要素」を指す
💡
重複検出
現在の要素がnums[write-2]と同じなら3個目の重複
💡
最大2個制約
この比較により各要素の出現回数を2回以下に制限