LeetCode の問題 132 Pattern への再挑戦の記録

O(n^2) のアルゴリズムしか思いつかなかった LeetCode の問題 132 Pattern に再挑戦するログです。

O(n * log(n)) のアルゴリズム

• Runtime: 7ms
• Your runtime beats 56.75 % of java submissions.

考え方

• サブシーケンスの真ん中の数値、すなわちサブシーケンスの中で最も大きい数値になったつもりで考えてみよう
• 長さ n (n == nums.length) の追加の配列 leftMinValues を用意しておく
• 配列 nums 上のあるインデックス j において、(j を含みつつ) それより左側の領域に存在している最小の数値を求めて長さ leftMinValues[j] に記録していく
  • この処理は nums を左から右に走査することで時間計算量 O(n) で達成できる
• 続いて、nums を 右から左に走査 し、(j を含まず) j より右側の領域に存在している nums[j] の次に小さい数値が存在するかを確認する
  • 存在していて、その数値が leftMinValues[j] より大きければ、132 pattern が存在する ことになる
  • 「nums[j] の次に小さい数値」を得るために、TreeSet を用いる
    • これにより O(n * log(n)) の時間計算量となる

コード

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }

        // インデックス j を含む左側の領域に存在する数値の最小値を求めていく
        // Time complexity: O(n)
        // Space complexity: O(n)
        int[] leftMinValues = new int[nums.length];
        leftMinValues[0] = nums[0];
        for (int j = 1; j < leftMinValues.length; j++) {
            leftMinValues[j] = Math.min(leftMinValues[j - 1], nums[j]);
        }

        TreeSet<Integer> rightValues = new TreeSet<>();
        rightValues.add(nums[nums.length - 1]);

        // インデックス j より右側に、nums[j] より小さくインデックス j より左側の最小値よりも大きい数値が存在するかを確認していく
        // Time complexity: O(n * log(n))
        // Space complexity: O(n)
        for (int j = nums.length - 2; j >= 0; j--) {
            if (leftMinValues[j] + 1 < nums[j]) {
                Integer candidate = rightValues.lower(nums[j]);
                if (candidate != null && candidate > leftMinValues[j]) {
                    return true;
                }
            }

            rightValues.add(nums[j]);
        }

        return false;
    }
}