# C++ solution 24ms with O(N) time and O(K) space by using set

• ``````class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int size = nums.size();
int maxElements = k + 1;
// the difference between first and last element is at most k
if (size <= maxElements)
{
set<int> s(nums.begin(), nums.end());
return s.size() != size;
}

set<int> s(nums.begin(), nums.begin() + maxElements);
for (int i = maxElements; i < size; i++)
{
if (s.size() != maxElements)
return true;

s.erase(nums[i - maxElements]);
s.insert(nums[i]);
}
return s.size() != maxElements;
}
};
``````
1. Using a set to determine if any element repeats.
2. For example, nums = { 1, 2, 3, 1, 3 } and k = 2
3. Add all elements with index <= k to set s = { 1, 2, 3 }, and start for loop from k + 1 to the end of nums
4. erase num[0] from set s and insert num[k + 1] to s, s = { 2, 3, 1 }
5. erase num[1] from set s and insert num[k + 2] to s, s = { 3, 1 }
6. If the size of set s is less than k + 1 at any step, it indicates duplicate items.

• Thanks for giving the answer!

But I dont think the time would be O(N) because you cannot guarantee that the time of a K size set insert and erase element is O(1).

Infact I thik your time should be O(N*log(k)). As far as i know , the STL set inster or erase an element with size k should be logk .

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.