0Pricing
Coding Interview Prep · レッスン

系列内のギャップを見つける

欠損値と、それぞれのギャップの開始点・終了点を検出します。

「系列内のギャップを見つける」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

ギャップを探す

ここまでは、行をアイランドにまとめてきました。これと対になる面接問題は、どの値が欠けているかです。面接官は、「このIDシーケンスのギャップを見つけてください」「どの請求書番号が抜けていますか」「活動がなかった日はいつですか」といった形で質問します。

ギャップとは、アイランドの間にある空白部分です。通常、欠落している値を1つずつ列挙する必要はありません。必要なのは、各ギャップ範囲の開始値と終了値を報告することであり、こちらのほうがはるかに簡潔で、面接官が期待する形式です。

ギャップのサンプルデータ

seq(n) テーブルにある既存の値 1、2、3、7、8、10 を再利用します。報告するギャップは次のとおりです。

  • 4から6まで（最初のアイランドの後、7の前）
  • 9から9まで（8と10の間）

ギャップは範囲として表します。gap_start = 最後に存在する値 + 1、gap_end = 次に存在する値 - 1 です。この簡潔な形式が、以下で扱う基本テクニックの目標です。

CREATE TABLE seq (n INT);
INSERT INTO seq VALUES (1),(2),(3),(7),(8),(10);

LEAD によるギャップ検出

最も明快なギャップ検出方法は、LEAD を使って各行と次の行を比較することです。次の値が現在の値より1を超えて大きければ、その間にギャップがあります。

そのような各行について、ギャップは n + 1 から始まり、next_n - 1 で終わります。まずは LEAD の生の出力を確認してください。

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

ギャップ範囲を報告する

LEAD の結果を CTE で囲み、次の値への増分が1を超える行だけを残します。それらの行がギャップを示します。

これにより、ギャップ4-6とギャップ9-9が正確に返されます。next_n - n - 1 という式からは、各ギャップに含まれる欠落値の個数も求められます。これは頻出する追加質問です。

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

対称的な LAG の方法

代わりに LAG を使い、前方向ではなく後方向を見ても同じギャップを検出できます。現在の行の前に、直前の値が現在の値より1を超えて小さい場合、ギャップが存在します。

これは完全に同等です。質問に対してより自然に読めるほうを選んでください。ギャップをその直前の行との関係で説明できるため、人が話すときの表現に合う LEAD を好む面接官もいます。

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

欠落値をすべて列挙する

面接官が範囲だけでなく、欠落している数値の完全な一覧を本当に求めることもあります。堅牢な方法は、期待される完全なシーケンスを生成し、存在する値に対してアンチ結合することです。Postgresでは、generate_series で範囲全体を生成できます。

期待される範囲内で、seq に存在しないすべての整数が欠落値になります。想定される最小値と最大値が分かっていれば、範囲の両端にあるギャップにも対応できます。

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

SQL方言ごとのシーケンス生成

すべてのエンジンに generate_series があるわけではありません。代替手段を把握しておきましょう。

  • Postgres：generate_series(1, 100)。
  • SQL Server：再帰 CTE または numbers/tally テーブル。
  • MySQL 8：最大値までカウントする再帰 CTE。

再帰 CTE は移植性の高い代替手段です。アンチ結合に使う同じ期待シーケンスを生成できます。

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

カレンダー日付のギャップ

欠落した日付を調べるには、日単位のステップで完全なカレンダーを生成し、アンチ結合します。これは「注文がなかった日はどれか」を調べる標準的なクエリです。

実際の日付に LEAD を適用する範囲のテクニックと組み合わせれば、個々の日ではなく欠落した日付の範囲を報告できます。境界には + INTERVAL '1 day' を使います。

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

データの範囲外にあるギャップ

見落としやすい落とし穴があります。LEAD/LAG で見つけられるのは、存在する値の間にあるギャップだけです。最小の既存値より前や最大の既存値より後に数値が欠けていても、隣接する行がないため、ウィンドウ関数の方法では検出できません。

面接官が期待される完全な範囲（たとえばID 1から100まで）を定義し、データが5から始まっている場合は、データ自身の最小値と最大値ではなく、宣言された範囲を境界とする generate-series anti-join を使う必要があります。期待される境界が固定されているか、必ず確認してください。

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

グループごとのギャップ検出

ユーザーごとのギャップを求めるには、グループ列で LEAD/LAG をパーティション分割します。これにより、異なるユーザーのストリームをまたぐギャップが報告されることはありません。

各ユーザーの欠落範囲が独立して計算されます。アイランドの場合と同様に、パーティション分割を忘れるとユーザーが暗黙に統合され、関係のない行にまたがる見せかけのギャップが生成されます。

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

適切なギャップ検出方法を選ぶ

面接での判断基準は次のとおりです。

  • 簡潔な範囲だけが必要で、データ内部のギャップのみを対象にする場合は、LEAD/LAG を使い、増分が1を超える行を絞り込みます。
  • 欠落値を1つずつすべて求める場合、またはデータの範囲外にあるギャップも対象にする場合は、宣言された完全な範囲に対して generate-series anti-join を使います。

両方の選択肢と、それぞれを使う場面に触れると、理解の深さが伝わります。LEAD の方法は低コストで、シーケンス生成の方法はより完全です。

確認問題

境界ケースの落とし穴を確認してください。

まとめ：ギャップの検出

これでギャップ検出は身につきました。

  • ギャップは範囲として報告します。gap_start = value + 1、gap_end = next_value - 1 です。
  • LEAD（または対称的な LAG）で増分が1を超える行を絞り込むと、内部ギャップを低コストで見つけられます。
  • generate-series anti-join は、欠落値をすべて列挙し、宣言された範囲に対する両端のギャップも検出します。
  • generate_series がない場合は、再帰 CTE でシーケンスを生成します。
  • ユーザーごとのギャップでは、グループ列でパーティション分割します。
  • 期待される境界は、必ず確認してください。

最後に、最も応用範囲の広いバリエーションである、日付とステータスの変化で定義されるアイランドを扱います。

よくある質問

「系列内のギャップを見つける」レッスンは無料ですか？

はい。「系列内のギャップを見つける」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「系列内のギャップを見つける」で何を学びますか？

欠損値と、それぞれのギャップの開始点・終了点を検出します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「系列内のギャップを見つける」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ギャップと島問題を見分ける
  2. 行番号の差分トリック
  3. 系列内のギャップを見つける
  4. 日付とステータスの変化で島を作る
← Coding Interview Prepに戻る