Array     C++     Easy     Hash Table     Sliding Window    

Problem Statement:

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

Solution:

The idea is to find if we have seen the current value already in the range. Since the search operation in hashset is constant time, hence our algorithm is efficient.

 
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        int n=nums.size();
        unordered_set<int> numset;
        for (int i=0; i<k && i<n; ++i)
        {
            if (numset.count(nums[i])) return true;
            numset.insert(nums[i]);
        }
        for (int i=k; i<n; ++i)
        {
            if (numset.count(nums[i])) return true;
            numset.insert(nums[i]);
            numset.erase(nums[i-k]);
        }
        return false;
    }
};
 
 
TC: O(n)
SC: O(k)