コーディング面接：二分探索で k 番目に欠落している正の整数を見つけるには？

面接官が評価するポイント

表面的な問題は配列内のカウントですが、本質は「インデックス i までにいくつの値が欠落しているか」を単調な述語に変換し、その境界を探索することです。LeetCode 1539 は公開された問題文と Amazon の問題セットのエントリを提供しています。Amazon の SDE ガイドラインでは、実行可能で堅牢、テスト済みであり、エッジケースが確認されているコードを重視しています。これらの情報源は準備としての価値を裏付けるものであり、特定の企業での面接出題頻度を保証するものではありません。

missing(i) = arr[i] - i - 1 を記述できるかどうか。
欠落数が非減少であることを証明できるかどうか。
配列の最後の要素を超える解を処理できるかどうか。
コントラクトに基づき、スキャン、二分探索、直接生成を比較できるかどうか。

30秒の回答フレームワーク

配列が 0-indexed であることを述べます。arr[i] までには、値の範囲内に arr[i] 個の正の整数が存在しますが、観測された要素は i + 1 個のみであるため、欠落数は arr[i] - i - 1 になります。missing(i) >= k を満たす最初のインデックスを二分探索します。それが i であれば、答えは k + i です。どのインデックスも満たさない場合、答えは配列の後にあり k + n となります。スキャンは O(n)、二分探索は O(log n) かかり、いずれも O(1) の追加空間を使用します。

回答前に確認すべき明確化のための質問

配列は正の整数であり、狭義の単調増加であることが保証されていますか？そうでない場合、ソートや重複排除によってコントラクトが変わります。
k は正数ですか？また、値はその言語の安全な整数範囲を超える可能性がありますか？
1 つの値のみが必要ですか、それとも欠落しているすべての値が必要ですか？すべての値を返す場合は出力コストが発生します。
入力はランダムアクセスなしのストリームとして与えられる可能性がありますか？その場合はスキャンが有利になることがあります。
元の配列を変更せずに保持する必要がありますか？二分探索の解法は配列を変更しません。

ステップごとの詳細解説

ステップ 1: 欠落数の計算式を構築する

配列が連続していれば、arr[i] は i + 1 に等しくなります。その差が [1, arr[i]] から欠落している正の整数の数になります：

text

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

arr = [2, 3, 4, 7, 11] かつ i=3 の場合、missing(3) = 7 - 3 - 1 = 3 となり、欠落している値は 1、5、6 です。

ステップ 2: 単調性を利用して境界を特定する

狭義の単調増加により arr[i+1] >= arr[i] + 1 が成り立ちます。したがって missing(i+1) >= missing(i) となり、カウントが減少することはありません。missing(i) >= k を満たす最初のインデックスを探索します。それ以前の要素はすべて欠落数が不足しており、そのインデックス以降はすべて k 以上の欠落数を持ちます。

ステップ 3: 境界から答えを復元する

境界を i とします。その前には i 個の観測された配列要素が存在し、境界の前にある欠落数は k 個未満です。したがって、k 番目に欠落している値は k + i です。境界が存在しない場合、最終的な欠落数は依然として k 未満であり、観測された n 個の要素はすべて答えより前に位置するため、結果は k + n になります。

ステップ 4: 二分探索を実装する

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

right = n を使用することで、境界が配列の直後に位置することが許容されます。終了時、left は欠落数が k に達する最初の位置となるため、同じ k + left の式で両方のケースを処理できます。

ステップ 5: 計算量を証明し境界をテストする

各反復で探索区間が半分になるため、計算量は O(log n) 時間、追加変数は定数個となります。6 に対する arr = [1,2,3,4], k = 2、9 に対する arr = [2,3,4,7,11], k = 5、1 から欠落しているシーケンス、連続した末尾、k=1、要素が 1 つの配列をテストします。また、選択した言語における整数の境界値も確認します。

模範的な高評価の回答

インデックス i までの欠落している正の整数の数を arr[i] - i - 1 として定義します。配列は狭義の単調増加であるため、そのカウントは単調であり、カウントが k 以上となる最初のインデックスを二分探索します。境界が i の場合、k 番目に欠落している値は k + i です。右の境界を n に設定することで、配列の最大値を超える答えを自然に処理できます。

半開区間 [left, right) を使用します。missing(mid) が k より小さい場合、境界は右側にあります。それ以外の場合は mid を維持します。結果は k + left となり、O(log n) 時間および O(1) 空間で動作します。先頭の欠落、末尾の欠落、連続した配列、単一要素、複数の k の値をテストし、スキャンベースのオラクルと比較します。

よくある間違い

arr[i] - i と記述し、1 を引く項を忘れる。
最後の偽の位置を探索しているのに、最初の真の回答式を使用してしまう。
right を n - 1 に設定し、配列の後の答えを適切に処理できない。
入力がソートされていない、または重複が含まれている場合にこの式を適用してしまう。
例題のみをテストし、[1,2,3]、[2]、または連続した末尾を見落とす。
ソートされた入力や小さい n の定数項について議論せずに、二分探索が常に高速であると主張する。

実装のトレードオフ

データサイズと境界のコントラクトから線形スキャンまたは二分探索を選択し、テストによって不変条件を検証します。

フォローアップの質問と回答

なぜ欠落数は単調なのですか？

狭義の単調増加とは、次の値が少なくとも 1 増加することを意味します。インデックスが 1 増えると値も少なくとも 1 増えるため、arr[i] - i - 1 は減少することがありません。

配列がソートされていない場合や重複がある場合はどうなりますか？

まずコントラクトを変更します。ソートし、重複を排除し、正の値を保持します。ソートには少なくとも O(n log n) のコストがかかり、その後に初めて元の欠落数計算式が適用されます。未ソートの入力に対して O(log n) であると主張してはいけません。

線形スキャンが好まれるのはどのような場合ですか？

短い配列、1 回限りのクエリ、またはランダムアクセスのないストリームの場合、スキャンのほうが単純です。二分探索はソート済みのランダムアクセス可能な入力を前提としており、セットアップや定数倍のオーバーヘッドがあります。

最初の k 個の欠落値を返すにはどうしますか？

値の境界を見つけた後、配列ポインタを使用して O(k) の出力時間で値を生成します。出力のための処理を O(log n) の主張の中に隠すことはできません。

大きな k や大きな値に対するオーバーフローをどのように防ぎますか？

安全な整数型または 64 ビット型を使用し、k + left と arr[i] - i - 1 を確認します。任意精度が許可されている場合は、インターフェースとテストで BigInt または同等の表現を指定します。

評価基準（ルーブリック）

評価軸	合格の証拠	不合格のシグナル
モデリング	インデックスの説明を伴う正しい欠落数の式	1 を引く項の欠落
二分探索	最初の真となる境界を見つけている	最初の真と最後の偽の式を混同している
境界処理	配列外の答えを一意に処理している	`arr[n]` を読み出す、または末尾のケースをスキップする
エンジニアリング	計算量、オーバーフロー、オラクルテストを網羅している	検証なしでコードのみを提示する

優れた候補者は、単調な述語を導出し、半開区間の探索を実装し、回答の式を説明します。コードを覚えているだけで境界を証明できない候補者には、さらなる質問が必要です。