C++ Coding Exercise – How to Check Duplicates with Sliding Window?

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 difference between i and j is at most k.

Submit your solution: https://leetcode.com/problems/contains-duplicate-ii/

Using Map

We can use STL::map data structure to store the last index for a given number. Thus, we can check if the current index is within the k-window. We need to update at each iteration the last index.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            int cur = nums[i];
            if (cache.count(cur)) {
                int last = cache[cur];
                if (i - last <= k) { // at most k
                    return true;
                }
            }
            cache[cur] = i; // updated the last index
        }
        return false;
    }
};

Sliding Window

We can use unordered_set as well to store all numbers within the k-window. Then we need to update (insert or erase) numbers at each iteration.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> uset;
        int size = nums.size();
        int w = 0;
        for(int i = 0;i < size; ++i){
            if(i - w > k){
                uset.erase(nums[w++]); // out of the sliding window
            }
            auto r = uset.insert(nums[i]); // include the new number
            if(!r.second) {
                return true; 
            }
        }
        return false;
    }
};

Note that the STL::set.insert function returns the pair that the second value when equal false represents that the value has existed in the set before the insertion. It is equivalent to the following:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> uset;
        int size = nums.size();
        int w = 0;
        for(int i = 0;i < size; ++i){
            if(i - w > k){
                uset.erase(nums[w++]); // out of the sliding window
            }
            if (uset.count(nums[i])) {
                return true;
            }
            uset.insert(nums[i]);
        }
        return false;
    }
};

All above solutions have complexity O(n).

–EOF (The Ultimate Computing & Technology Blog) —