Description:
Given an integer array nums and an integer k, return trueif there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Examples:
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: falseSolution in Python:
Python
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# Dictionary to store the index of the last occurrence of each element
index_map = {}
# Iterate through the array
for i, num in enumerate(nums):
# Check if the element is in the dictionary
if num in index_map:
# Check if the difference between indices is less than or equal to k
if i - index_map[num] <= k:
return True
# Update the dictionary with the current index of the element
index_map[num] = i
# If no such pair is found, return false
return FalseExplanation of the Code:
- Dictionary Initialization:
index_mapis initialized as an empty dictionary. This will map each element innumsto its latest index. - Loop Through the Array: We use
enumerate(nums)to get both the indexiand the elementnum. - Check for Previous Occurrence:
- If
numis already a key inindex_map, it means we have encountered this element before. - We then check if the difference between the current index
iand the index stored inindex_mapis less than or equal tok. If it is, we returnTrue.
- If
- Update the Dictionary: Whether or not the distance condition is met, we update
index_mapto set the current indexias the latest index for the elementnum. - Return False: If we complete the loop without finding any pair of indices that meet the criteria, we return
False.
This approach ensures that we are efficiently checking for the condition in a single pass through the array, making it an optimal solution with a time complexity of O(n) and space complexity of O(n).
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
// Object to store the index of the last occurrence of each element
let indexMap = {};
// Iterate through the array
for (let i = 0; i < nums.length; i++) {
let num = nums[i];
// Check if the element is in the object
if (indexMap.hasOwnProperty(num)) {
// Check if the difference between indices is less than or equal to k
if (i - indexMap[num] <= k) {
return true;
}
}
// Update the object with the current index of the element
indexMap[num] = i;
}
// If no such pair is found, return false
return false;
};Solution in Java:
Java
import java.util.HashMap;
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// HashMap to store the index of the last occurrence of each element
HashMap<Integer, Integer> indexMap = new HashMap<>();
// Iterate through the array
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
// Check if the element is in the map
if (indexMap.containsKey(num)) {
// Check if the difference between indices is less than or equal to k
if (i - indexMap.get(num) <= k) {
return true;
}
}
// Update the map with the current index of the element
indexMap.put(num, i);
}
// If no such pair is found, return false
return false;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public bool ContainsNearbyDuplicate(int[] nums, int k) {
// Dictionary to store the index of the last occurrence of each element
Dictionary<int, int> indexMap = new Dictionary<int, int>();
// Iterate through the array
for (int i = 0; i < nums.Length; i++) {
int num = nums[i];
// Check if the element is in the dictionary
if (indexMap.ContainsKey(num)) {
// Check if the difference between indices is less than or equal to k
if (i - indexMap[num] <= k) {
return true;
}
}
// Update the dictionary with the current index of the element
indexMap[num] = i;
}
// If no such pair is found, return false
return false;
}
}