Algorithm

Problem Name: 219. Contains Duplicate II

Problem Link: https://leetcode.com/problems/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

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct {
    int val;
    int idx;
} e_t;
int cmp(void const *a, void const *b) {
    return ((const e_t *)a)->val  <  ((const e_t *)b)->val ? -1 :
           ((const e_t *)a)->val > ((const e_t *)b)->val ?  1 :
           ((const e_t *)a)->idx < ((const e_t *)b)->idx ? -1 : 1;
}
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    e_t *p;
    int i, f;
    
    p = malloc(numsSize * sizeof(e_t));
    //assert(p);
    for (i = 0; i  <  numsSize; i ++) {
        p[i].val = nums[i];
        p[i].idx = i;
    }
    
    qsort(p, numsSize, sizeof(e_t), cmp);
    
    f = 0;
    for (i = 1; !f && i  <  numsSize; i ++) {
        if (p[i].val == p[i - 1].val &&
            p[i].idx - p[i - 1].idx <= k) f = 1;
    }
    
    free(p);
    
    return f;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,2,3,1], k = 3

Output

x
–
+
cmd
true

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map map = new HashMap<>();
    for (int i = 0; i  <  nums.length; i++) {
      if (map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k) {
        return true;
      }
      map.put(nums[i], i);
    }
    return false;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,2,3,1], k = 3

Output

x
–
+
cmd
true

#3 Code Example with Javascript Programming

Code - Javascript Programming


const containsNearbyDuplicate = function(nums, k) {
    const map = new Map();
    for (let i = 0; i  <  nums.length; i++) {
        if (map.has(nums[i])) {
            if (i - map.get(nums[i]) <= k) {
                return true;
            } else {
                map.set(nums[i], i);
            }
        } else {
            map.set(nums[i], i);
        }
    }
    return false;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,0,1,1], k = 1

Output

x
–
+
cmd
true

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        dic={}
        for i,num in enumerate(nums):
                if num in dic and i-dic[num]<=k:
                    return True
                dic[num]=i
        return False
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,0,1,1], k = 1

Output

x
–
+
cmd
true

#5 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0219_ContainsDuplicateII
    {
        public bool ContainsNearbyDuplicate(int[] nums, int k)
        {
            var map = new Dictionary < int, int>();
            for (int i = 0; i  <  nums.Length; i++)
            {
                if (map.ContainsKey(nums[i]) && i - map[nums[i]] <= k)
                    return true;
                map[nums[i]] = i;
            }

            return false;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
nums = [1,2,3,1,2,3], k = 2

Output

x
–
+
cmd
false
Advertisements

Demonstration

Previous
#218 Leetcode The Skyline Problem Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#220 Leetcode Contains Duplicate III Solution in C, C++, Java, JavaScript, Python, C# Leetcode