219.contains-duplicate-ii.md

219. Contains Duplicate II

Brute Force

We can iterate every number in the array, then check if there is a duplicate within k distance.

fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
    val n = nums.size
    for (i in 0 until n) {
        // Check ascendingly
        for (j in i + 1..i + k) {
            if (j < n && nums[i] == nums[j]) return true
        }
        // Check descendingly
        for (j in i - 1 downTo i - k) {
            if (j >= 0 && nums[i] == nums[j]) return true
        }
    }
    return false
}

• Time Complexity: O(n^2).
• Space Complexity: O(1).

Hash Table (Fixed-size Sliding Window)

There is duplicate check if the two index within k distance from brute force approach. For example, k = 3:

• When we check index 0, then we will check index 1, 2, 3 in ascending order.
• When we check index 3, then we will check index 2, 1, 0 in descending order.

index = 0, 1, 2, 3, 4, 5, 6, 7, 8
        i ->
              <- i

We can improve this by maintaining a set of size k, check if the number exists in the set.

index = 0, 1, 2, 3, 4, 5, 6, 7, 8
                 i
        |--------|

And remove the element of index i - k - 1 from set when we move to the next index.

index = 0, 1, 2, 3, 4, 5, 6, 7, 8
                    i
           |--------|
        ^ // Remove it from set

fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
    val seen = HashSet<Int>()
    for (i in 0 until nums.size) {
        if (i - k - 1 >= 0) {
            seen.remove(nums[i - k - 1])
        }
        if (seen.contains(nums[i])) return true
        seen.add(nums[i])
    }
    return false
}

• Time Complexity: O(n).
• Space Complexity: O(k).

Sliding Window

Similar idea from hash table above. We can maintain a window of abs(i - j) <= k where i, j are distinct indices, and check if there is a duplicate number in the window.

fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
    var left = 0
    var right = 0
    val map = HashMap<Int, Int>()
    while (right < nums.size) {
        map[nums[right]] = (map[nums[right]] ?: 0) + 1
        while (right - left > k) {
            map[nums[left]] = (map[nums[left]] ?: 0) - 1
            left++
        }
        // Problem description: abs(i - j) <= k
        if (right - left <= k && (map[nums[right]] ?: 0) > 1) return true
        right++
    }
    return false
}

• Time Complexity: O(n).
• Space Complexity: O(k).

Or similar idea, we can use hash map to store the value and index, then check if the value exists in the map and the distance between current index and index from map is within k. For example:

index =  0  1  2  3       6  7  ...
value = [x, x, 5, x, ..., x, 5, ...] 
                             * 

map = {
    5: 2
    ...
}

Current index = 7, value = 5, and map[5] is 2, that indicates previous 5 occures at 2, then we check the distance (7 - 2) is within k.

fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
    // value -> index
    val hashMap = HashMap<Int, Int>()
    for (i in 0 until nums.size) {
        val value = nums[i]
        if (hashMap.containsKey(value)) {
            val index = hashMap[value]!!
            val distance = i - index
            if (distance <= k) return true
        }
        hashMap[value] = i
    }
    return false
}