競プロでは時間計算量が重視されますが空間計算量に注目して解くのも楽しいよというお話です。

Extra time complexityとは

突然ですが、次のような問題を考えてみましょう。

https://leetcode.com/problems/single-number/

問題概要

ひとつの値を除いて、同じ値がちょうど二回ずつ現れる整数列(例えば[1,1,2,2,3]のようなもの)が与えられたとき、一度しか現れない値を求めよ

解法

これは例えばunordered_mapを使って各値の出現回数をメモすれば解けます。

int solve(vector<int> &nums) {
    unordered_map<int, int> mp;
    for(auto &e : nums) {
        mp[e]++;
    }
    for(auto &e : nums) {
        if(mp[e] == 1)
            return e;
    }
}

この解法の計算量は時間計算量 $O(n)$ 、空間計算量 $O(n)$ となります。

さてここで問題の注釈を見ると追加の条件として

Could you implement a solution with a linear runtime complexity and without using extra memory?

とあります。ここで一応用語を定義しておきます。

与えられた入力の分の空間計算量を除いた空間計算量のことを extra space complexityとよぶ

この問題の追加の条件は言い換えると $O(1)$ の extra space complexityで解けということになります。（全く他のメモリを使うなという風にも解釈できますが、どうやらそうではないようです）上の解法では与えられた配列numsに加えてunordered_mapを使っているのでO(n)分の追加の空間計算量がかかってしまい不適です。

実は排他的論理和を使うとこの問題は $O(1)$ extra time complexityで次のように解けます。

解法

初期値0のint型の変数aを用意してnumsの各要素との排他的論理和を取っていけば、最後のaの値がnumsで一度しか現れない値となります。なぜなら同じ数同士の排他的論理和は $0$ となるので二回現れる数は最終的には消えてしまい、一度しか現れない数だけが残るからです。

int solve(vector<int> &nums) {
    int a = 0;
    for(auto &e : nums) {
        a ^= e;
    }
    return a;
}

この解法では変数aだけを用いているのでこの解法のextra space complexityはO(1)です。

問題

以下 $O(1)$ extra time complexityを要求される問題を何問か紹介しようと思います。

Missing Number

https://leetcode.com/problems/missing-number/

問題概要

長さ $n$ の配列に $0\sim n$ の範囲の整数が重複なく入っています、 $0\sim n$ のうち配列に現れない数を $O(1)$ extra space complexityで出力してください

解法

$S$ を $0$ から $n$ までの和とします。配列の各要素を $S$ から引いていくと最後の $S$ の値が配列に現れない数となります。新たな変数として $S$ しか用いていないので $O(1)$ extra space complexityで解けました。

Increasing Triplet Subsequence

https://leetcode.com/problems/increasing-triplet-subsequence/

問題概要

与えられた整数列から単調増加となるような長さ $3$ の部分列が取れるかどうかを $O(1)$ extra space complexityで判定してください

解法

$O(1)$ extra space complexityを気にせず解くならば真ん中の数に注目して左右に自分より小さい数と大きい数があるか判定する解法が自然でしょうか。これは前からの累積minと後ろからの累積maxを使えばできますがそれらを保存するのに $O(n)$ の空間計算量が必要となります。 $O(1)$ extra space complexityで解くなら次のように貪欲に1番目と2番目の要素を決めていき、三番目の要素が条件を満たすかを判定すれば良いでしょう。

変数firstとsecondを用意する
数列を前から見ていき
- secondより大きいならtrueを返す
- firstより大きくsecondより小さいならsecondを更新
- first以下ならfirstを更新
最後まで見てもtrueを返してないならfalseを返す

上の手順では一見firstを更新したときsecondが更新されず、firstとsecondが逆になるかもしれませんが（入力例として[3,4,1,5]などで発生する）、3番目の要素の候補がsecondより大きければ、現時点でのfirst及び更新前のfirstよりも大きいので結局答えはtrueになります。

bool solve(vector<int> &nums) {
    int n = nums.size();
    if(n < 3) {
        return false;
    }
    int first = nums[0], second = INT_MAX;
    for(int i = 1; i < n; i++) {
        if(nums[i] > second) {
            return true;
        }
        if(nums[i] <= second && nums[i] > first) {
            second = nums[i];
        }
        if(nums[i] <= first) {
            first = nums[i];
        }
    }
    return false;
}

これなら追加の空間計算量は3つ変数を追加しただけなので $O(1)$ extra space complexityを達成できました。

First Missing Positive

https://leetcode.com/problems/first-missing-positive/

問題概要

与えられた整数列に出現しない最小の自然数を $O(1)$ extra space complexityで出力せよ

解法

整数列の長さを $n$ とします。重要な考察として整数列に出現しない最小の自然数は $1\sim n+1$ の範囲に必ずあります。よって整数列のうち $1\sim n$ までの数の出現をメモすればこの問題は解けます。しかしこれは空間計算量 $O(n)$ となってしまい不適です。この問題を解くには入力の整数列用の配列を再利用します。この先は1-indexで話を進めます。また整数列を $a_1,\ldots, a_n$ とします。以下のような手順で $a_1 ,\ldots, a_n$ に現れる $1\sim n$ までの数の出現を $a_1 \ldots a_n$ に直接メモしていきます。

整数列のうち0以下の要素を全て $n+1$ に置き換える（これにより全ての要素は正になる）
全ての $1\leq i \leq n$ について $1\leq abs(a_i)\leq n$ かつ [tex:a{abs(a_i)}]が正ならば[tex:a{abs(a_i)}]を $-1$ 倍する
$a_1\ldots a_n$ のうち初めて正である要素のインデックスが与えられた整数列に出現しない最小の自然数と一致するので出力する、存在しないならば $n+1$ を出力する

このように数列の符号を直接書き換えることによって数の出現を追加の空間計算量を使うことなくメモしていくことができ $O(1)$ extra space complexityでこの問題が解けました。

int n = nums.size();
    for(int i = 0; i < n; i++) {
        if(nums[i] <= 0) {
            nums[i] = n + 1;
        }
    }
    for(int i = 0; i < n; i++) {
        if(abs(nums[i]) <= n && nums[abs(nums[i]) - 1] > 0) {
            nums[abs(nums[i]) - 1] *= -1;
        }
    }
    for(int i = 0; i < n; i++) {
        if(nums[i] > 0) {
            return i + 1;
        }
    }
    return n + 1;

Find the Duplicate Number

最後の問題です。youtubeで558万回再生されたほどの超有名な問題です。

https://leetcode.com/problems/find-the-duplicate-number/

問題概要

長さ $n+1$ の整数列が与えられます。各要素は $1\sim n$ の範囲に収まっています。更に数列内に重複して現れる数は1種類であることが保証されます。数列内で重複して現れる数を $O(1)$ extra space complexity出力してください、ただし追加の制約として与えられた数列を書き換えてはいけません

解法

追加の制約よりさっきの問題のように元の数列の値をいじることでメモリを再利用することもできません。この問題は二分探索による時間計算量 $O(n\log n)$ かつ $O(1)$ extra space complexityで解くことができます。ある値 $X$ を決めたとき数列の全ての要素のうち $X$ 以下の要素の個数を $c$ とします。これは $X$ が重複している数より小さいときは $c \leq X$ となります。なぜなら $X$ が重複している数より小さいときは $1\sim X$ までの数は高々1回しか現れないので $c$ は最大でも $X$ にしかなりません。同様に考えると、逆に $X$ が重複している数以上のときは $c \gt X$ になります。この性質からXを二分探索することで重複する数を探すことができます。

int solve(vector<int> &nums) {
    int l = 0, r = nums.size() + 1;
    int c;
    while(l + 1 < r) {
        c = 0;
        for(int &elem : nums)
            c += (elem <= (l + r) / 2);
        if(c <= (l + r) / 2)
            l = (l + r) / 2;
        else
            r = (l + r) / 2;
    }
    return r;
}

変数を3個追加しているだけなので時間計算量 $O(n\log n)$ かつ $O(1)$ extra space complexityで解けました。

別解

実はこの問題は時間計算量 $O(n)$ かつ $O(1)$ extra space complexityで解けることが知られています。数列をnumsとすると、各要素は $1\sim n$ の範囲に収まっているので次のような遷移を考えることができます(1-indexとします)。

x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ....

この遷移からループのある連結リストを構成できます。例えば数列[2,6,4,1,3,1,5]において2からスタートすると

2->4->3->1->6->5->1->6->5->1->6->5->...

という感じになり、1->6->5をループします。このループの入り口の数が重複する数となります。よってループの入り口を検出すれば良いことになりますが、これはFloyd's cycle-finding algorithmによって行うことができます。そしてFloyd's cycle-finding algorithmは実は $O(1)$ extra space complexityのアルゴリズムとなっています。よってこの問題が時間計算量 $O(n)$ かつ $O(1)$ extra space complexityで解けます。