Contains Duplicate II

Problem

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.

Constraints

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

Solution

The problem Contains Duplicate II can be solved using the technique from Contains Duplicate except this time, map is used instead of set to keep track of last found index for a given value.

Implementation

class Solution
{
  public:
    bool containsNearbyDuplicate(vector<int> &nums, int k)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        unordered_map<int, int> hashmap;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hashmap.find(nums[i]) != hashmap.end() && i - hashmap[nums[i]] <= k)
                return true;
            hashmap[nums[i]] = i;
        }
        return false;
    }
};