LeetCoding Challenge Oct. 1: Number of Recent Calls

LeetCode のデイリーチャレンジに挑んだログを気の赴くままに、かつ解けた場合にメモとして残しておくことにします。

今日は Number of Recent Calls です。

問題の概要

• 直近 3,000 ミリ秒内の ping() 回数を返す RecentCounter クラスを実装する

実装の手順・考え方の推移

• とりあえず、ナイーブに ping() をコールしたときの時刻をすべて保持しておこうかな
  • TreeSet を使えば、 TreeSet#tailSet(t - 3000) で直近 3,000 ミリ秒以内のコール回数は簡単に求められるね
  • (この時点ではちゃんと constraints を確認してなかったが…) すべて保持することでヒープを食い潰すようなら TreeSet#headSet(t - 3000) の要素を削除する実装にすればいいし
• 実際に実装して submit → accept された 🤗
  • しかしとても遅く、700ms 超えてしまっている 😫
• 速度パフォーマンスに着目して最適化しよう 💪
• TreeSet は色々とオーバーヘッドが大きいので、プリミティブな int 配列もしくは ArrayList<Integer> で置き換えよう
  • ping() の引数 t は前回コールの値より必ず大きな値となるので、長さ 3,000 の int 配列をリングバッファとして用意すればいいか
  • 直近 3,000 ミリ秒以内における、最も古い時刻のバッファ上の要素を指し示すインデックスをメンバ変数 left で表し、また最も新しい方のインデックスを right で表そう
    • left, right を [0, 3000) の範囲で表そうとすると left < right のあたりで面倒くさいことになりそうなので、times[left % 3000] みたいな感じでリングバッファを参照することにしよう
  • でも剰余演算はちょっと重いし、リングバッファを余分に大きめに確保しておいて times[left & MASK] みたいにビットマスクをかける方式に変えよう
  • left は ping() が呼ばれる度に必要な分だけインクリメントすることになるが、これの時間計算量は過去 m ミリ秒のコール回数を計測するとした場合に O(m) となるのかな
    • 今回は m は変化しないので定数時間と解釈していいはず…
• int 配列を使う方法で実装し直して submit → accept された 🤗
  • 速度は 16ms で Your runtime beats 99.74 % of java submissions. ということなので、まずまず満足できた
    • 最速なのは 15ms ぽい

最終的なコード

class RecentCounter {
    private static final int BUF_SIZE = 1 << 12;
    private static final int MASK = BUF_SIZE - 1;

    private int[] times = new int[BUF_SIZE];
    private int left;
    private int right;

    public RecentCounter() {
    }

    public int ping(int t) {
        times[right & MASK] = t;
        right++;

        while (left < right && times[left & MASK] < t - 3000) {
            left++;
        }

        return right - left;
    }
}