Contains Duplicate II Problem


Description

LeetCode Problem 219.

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
}




Related Posts

Contains Duplicate Problem

LeetCode 217. Given an integer array nums, return true if...

Contains Duplicate II Problem

LeetCode 219. Given an integer array nums and an integer...

Bulls And Cows Problem

LeetCode 299. You are playing the Bulls and Cows game...

Repeated DNA Sequences Problem

LeetCode 187. The DNA sequence is composed of a series...

Majority Element Problem

LeetCode 169. Given an array nums of size n, return...

Fraction To Recurring Decimal Problem

LeetCode 166. Given two integers representing the numerator and denominator...