Contains Duplicate (#217, #219 Leetcode)

 Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> uos;
        uos.insert(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (uos.find(nums[i]) != uos.end()) {
                return true;
            }
            uos.insert(nums[i]);
        }
        
        return false;
    }
};

unordered_map will be used to store key-value pairs, here the duplicate count is not asked.

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    
    unordered_map<int,int> nmap;
    for (int i = 0; i <nums.size();i++)
    {
        if (nmap.count(nums[i]) == 0)
            nmap[nums[i]] = i;
        else if (i - nmap[nums[i]] <=k) {
            return true;
        } else {
            nmap[nums[i]] = i;
        }
    }
    
    return false;
    
}
};

If the input given is [1,2,3,1, 2, 3] and k is 2, the map will contain the elements in this order after each iteration.

Output

After 0 iteration
1 0

After 1 iteration
2 1
1 0

After 2 iteration
3 2
2 1
1 0

After 3 iteration
3 2
2 1
1 3

After 4 iteration
3 2
2 4
1 3

After 5 iteration
3 5
2 4
1 3

If we want to update the element in the same key, the old value will be destroyed. It will store the new value.