[LeetCode Road] Contains Duplicate II - Solution/C++

219. Contains Duplicate II

Question:

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.

Example:

Input: nums = [1,2,3,1], k = 3
Output: true

Input: nums = [1,0,1,1], k = 1
Output: true

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Source code

Version 1

Idea:
I use unordered_map to implement the approach.
Use find() to check nums[n] whether it's exist in container or not. If it cannot find the element, insert nums[i]as a key and i index as a value in container. If the element is found, check the distance between current index i and it->second (previous index), it should less than or equal to k.
Notice, if i - it->second is bigger than k, you must update it->second to current index i at 12 line.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> record;
        unordered_map<int, int>::iterator it;
        const int n = nums.size();
        
        for(int i = 0; i< n; i++){
            it = record.find(nums[i]);
            if(it != record.end()){
                if(i - it->second <= k) return true;
                it->second = i;
            }else{
                record.insert(pair<int, int>(nums[i], i));
            }
        }
        return false;
    }
};

Version 2

Idea:
This method is unordered_set. I have introduced unordered_set function at Contains Duplicate.
Hence, use unordered_set is more efficient than unordered_map of memory usage.
At 6 line, it always maintains latest k elements of nums, to ensure the distance isn't exceed k between i and j. If i > k, use erase(elements) to remove the specific element in the container.

Also, if the element of index i has exist in the container already, it will return false at 8 line, then retun true.

Time complexity: O(n)
Space complexity: O(min(n, k))

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> record;
        for(int i = 0; i < nums.size(); i++){
            if(i > k) record.erase(nums[i - k - 1]);
            
            if(!record.insert(nums[i]).second) return true;
        }
        return false;
    }
};