Home
C++ Coding Exercise – How to Check Duplicates with Sliding Window?
Tags:, , ,

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

April 12, 2016 1 Comment c / c++, data structure, leetcode online judge

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;
    }
};
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
    }
};
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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;
    }
};
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) —

GD Star Rating
loading...
441 words
Last Post: Nth Highest Distinct Record using SQL
Next Post: How to Add Binary String in C/C++?

The Permanent URL is: C++ Coding Exercise – How to Check Duplicates with Sliding Window?

Related posts:

  1. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...
  2. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  3. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  4. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  5. How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)? Given a binary search tree and the lowest and highest boundaries as L and R,...
  6. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  7. Characteristic Attributes Essential for Successful Software Engineers Passion for Learning Technology evolves, and as a software engineer, you would need a passion...
  8. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...

One Response

  1. Nick Sifniotis

    Do they? The complexities of the map and set functions are constant time are they?

    Reply

Leave a Reply