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.
This article is for beginners. It introduces the following ideas:\nLinear Search, Binary Search Tree and Hash Table.
\nIntuition
\nLook for duplicate element in the previous elements.
\nAlgorithm
\nThis 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.
\nJava
\npublic 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
\nTime complexity : .\nIt costs time for each linear search. Apparently we do at most comparisons in one search even if can be larger than .
\nSpace complexity : .
\nIntuition
\nKeep a sliding window of elements using self-balancing Binary Search Tree (BST).
\nAlgorithm
\nThe 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:
\ntrue if foundfalseJava
\npublic 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
\nTime 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 .
Space complexity : .\nSpace is the size of the sliding window which should not exceed or .
\nNote
\nThe algorithm still gets Time Limit Exceeded for large and .
\nIntuition
\nKeep a sliding window of elements using Hash Table.
\nAlgorithm
\nFrom 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.
true if foundfalseJava
\npublic 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
\nTime complexity : .\nWe do operations of search, delete and insert, each with constant time complexity.
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