Leetcode 219. Contains Duplicate II

Problem

配列に2つの同じ要素が含まれているかどうか、かつその場合それぞれの位置の差はk以内であるかを判定します。

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

InputとOutputの例は次になります。

Input: nums = [1,2,3,1], k = 3
Output: true

Approach #1 Naive Linear Search

リスト内の全ての要素に対して隣接要素を検査し、その差の絶対値がk以下であるかどうかをチェックするというアプローチをとっています。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        for i in range(len(nums)-1):
            for j in range(i+1, min(i+k+1, len(nums))):
                if nums[i] == nums[j]:
                    return True
        return False

この解法では、計算量は下記の様になります。

• Time complexity: O(nk)。それぞれの要素に対して最大k個の他の要素を確認します。nは配列の長さです。

• Space complexity: O(1)。追加のデータ構造を使用していません。

Leetcodeでは、TLEになります。Time complexityを効率化できるよう、Approach #2, #3を考えていきます。

Approach #2 Hashmap

アイデアとしては、各数値とその最新のインデックスをハッシュマップに保存します。各要素を順に見ていき、ハッシュマップ内に既にその要素が存在していれば、そのインデックスとハッシュマップに保存されたインデックスとの差がk以下であるかをチェックします。もし差がk以下であればTrueを返し、そうでなければハッシュマップを更新します。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        index_dict = {}
        for i in range(len(nums)):
            if nums[i] in index_dict:
                j = index_dict[nums[i]]
                if abs(i-j) <=k :
                    return True
                    
            index_dict[nums[i]] = i
        
        return False

たとえば、入力が nums = [1,2,3,1], k = 3の際には、下記のように HashMap を更新していきます。

i: 0 , nums[i]: 1 , index_dict: {}
i: 1 , nums[i]: 2 , index_dict: {1: 0}
i: 2 , nums[i]: 3 , index_dict: {1: 0, 2: 1}
i: 3 , nums[i]: 1 , index_dict: {1: 0, 2: 1, 3: 2}

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。HashMapの挿入と検索は通常O(1)です。それぞれの要素に対してHashmapの検索及び挿入を実行します。

• Space complexity: O(n)。HashMapは配列内の要素を保存するため、空間計算量はO(n)です。

Approach #3 Sliding Window + HashSet

Window（一部の要素の集合）を配列全体に「スライド」させてスキャンする方法をSliding Windowと言います。直近k個の数字をWindowと考え、Setに保存していきます。Window内に重複した要素が存在するかどうかをチェックします。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        window_set = set()
        for i in range(len(nums)):
            if nums[i] in window_set:
                return True
            else:
                window_set.add(nums[i])
                if len(window_set) > k:
                    window_set.remove(nums[i-k])
        
        return False

この実装では、Windowの大きさがkを超える場合、そのWindowから最も古い要素を削除します。Window内に重複がある場合、その時点でTrueを返します。

たとえば、入力が nums = [1, 2, 3, 4, 5, 3, 4], k = 3の際には、下記のように HashSet を更新していきます。

i: 0 , nums[i]: 1 , window_set: set()
i: 1 , nums[i]: 2 , window_set: {1}
i: 2 , nums[i]: 3 , window_set: {1, 2}
i: 3 , nums[i]: 4 , window_set: {1, 2, 3}
i: 4 , nums[i]: 5 , window_set: {2, 3, 4}
i: 5 , nums[i]: 3 , window_set: {3, 4, 5}

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。HashSetの検索、挿入、削除は通常O(1)です。それぞれの要素に対してHashSetの検索、挿入、削除を実行します。

• Space complexity: O(1)。HashSetは、最大でk+1個の要素を保持します。したがって、空間計算量はO(k)となります。

今回、numsの最大の長さとkはどちらとも最大10^5となっています。そのため、Approach #2, #3ともに計算量の観点ではどちらでも問題ありません。一方で、実務でメモリが制約されている場合には、Approach #1が適しているケースもあるかもしれません。

Reference