## 219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

b'
\n\n

\n

\n

## Solution

\n
\n

#### Approach #1 (Naive Linear Search) [Time Limit Exceeded]

\n

Intuition

\n

Look for duplicate element in the previous elements.

\n

Algorithm

\n

This algorithm is the same as Approach #1 in Contains Duplicate solution, except that it looks at previous elements instead of all its previous elements.

\n

Another perspective of this algorithm is to keep a virtual sliding window of the previous elements. We scan for the duplicate in this window.

\n

Java

\n
`public boolean containsNearbyDuplicate(int[] nums, int k) {\n    for (int i = 0; i < nums.length; ++i) {\n        for (int j = Math.max(i - k, 0); j < i; ++j) {\n            if (nums[i] == nums[j]) return true;\n        }\n    }\n    return false;\n}\n// Time Limit Exceeded.\n`
\n

Complexity Analysis

\n
\n
• \n

Time complexity : .\nIt costs time for each linear search. Apparently we do at most comparisons in one search even if can be larger than .

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
\n

#### Approach #2 (Binary Search Tree) [Time Limit Exceeded]

\n

Intuition

\n

Keep a sliding window of elements using self-balancing Binary Search Tree (BST).

\n

Algorithm

\n

The key to improve upon Approach #1 above is to reduce the search time of the previous elements. Can we use an auxiliary data structure to maintain a sliding window of elements with more efficient `search`, `delete`, and `insert` operations? Since elements in the sliding window are strictly First-In-First-Out (FIFO), queue is a natural data structure. A queue using a linked list implementation supports constant time `delete` and `insert` operations, however the `search` costs linear time, which is no better than Approach #1.

\n

A better option is to use a self-balancing BST. A BST supports `search`, `delete` and `insert` operations all in time, where is the number of elements in the BST. In most interviews you are not required to implement a self-balancing BST, so you may think of it as a black box. Most programming languages provide implementations of this useful data structure in its standard library. In Java, you may use a `TreeSet` or a `TreeMap`. In C++ STL, you may use a `std::set` or a `std::map`.

\n

If you already have such a data structure available, the pseudocode is:

\n
\n
• Loop through the array, for each element do
\n
• Search current element in the BST, return `true` if found
• \n
• Put current element in the BST
• \n
• If the size of the BST is larger than , remove the oldest item.
• \n
\n
• \n
• Return `false`
• \n
\n

Java

\n
`public boolean containsNearbyDuplicate(int[] nums, int k) {\n    Set<Integer> set = new TreeSet<>();\n    for (int i = 0; i < nums.length; ++i) {\n        if (set.contains(nums[i])) return true;\n        set.add(nums[i]);\n        if (set.size() > k) {\n            set.remove(nums[i - k]);\n        }\n    }\n    return false;\n}\n// Time Limit Exceeded.\n`
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We do operations of `search`, `delete` and `insert`. Each operation costs logarithmic time complexity in the sliding window which size is . Note that even if can be greater than , the window size can never exceed .

\n
• \n
• \n

Space complexity : .\nSpace is the size of the sliding window which should not exceed or .

\n
• \n
\n

Note

\n

The algorithm still gets Time Limit Exceeded for large and .

\n
\n

#### Approach #3 (Hash Table) [Accepted]

\n

Intuition

\n

Keep a sliding window of elements using Hash Table.

\n

Algorithm

\n

From the previous approaches, we know that even logarithmic performance in `search` is not enough.\nIn this case, we need a data structure supporting constant time `search`, `delete` and `insert` operations.\nHash Table is the answer. The algorithm and implementation are almost identical to Approach #2.

\n
\n
• Loop through the array, for each element do
\n
• Search current element in the HashTable, return `true` if found
• \n
• Put current element in the HashTable
• \n
• If the size of the HashTable is larger than , remove the oldest item.
• \n
\n
• \n
• Return `false`
• \n
\n

Java

\n
`public boolean containsNearbyDuplicate(int[] nums, int k) {\n    Set<Integer> set = new HashSet<>();\n    for (int i = 0; i < nums.length; ++i) {\n        if (set.contains(nums[i])) return true;\n        set.add(nums[i]);\n        if (set.size() > k) {\n            set.remove(nums[i - k]);\n        }\n    }\n    return false;\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time complexity : .\nWe do operations of `search`, `delete` and `insert`, each with constant time complexity.

\n
• \n
• \n

Space complexity : .\nThe extra space required depends on the number of items stored in the hash table, which is the size of the sliding window, .

\n
• \n
\n