This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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## Summary

\n## Solution

\n

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

\n\n

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

\n\n

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

\n\n## See Also

\n\n

'
\n\n

\nThis article is for beginners. It introduces the following ideas:\nLinear Search, Binary Search Tree and Hash Table.

\n\n

**Intuition**

Look for duplicate element in the previous elements.

\n**Algorithm**

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.

\nAnother 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**

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

**Complexity Analysis**

- \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

**Intuition**

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

\n**Algorithm**

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.

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`

.

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 - Search current element in the BST, return
- Return
`false`

\n

**Java**

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

**Complexity Analysis**

- \n
- \n
Time complexity : . We do operations of

\n`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
Space complexity : .\nSpace is the size of the sliding window which should not exceed or .

\n \n

**Note**

The algorithm still gets Time Limit Exceeded for large and .

\n\n

**Intuition**

Keep a sliding window of elements using Hash Table.

\n**Algorithm**

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
- 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 - Search current element in the HashTable, return
- Return
`false`

\n

**Java**

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

**Complexity Analysis**

- \n
- \n
Time complexity : .\nWe do operations of

\n`search`

,`delete`

and`insert`

, each with constant time complexity. \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