Contains Duplicate Ii

                                            
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> numIndexMap;
        
        for (int i = 0; i < nums.size(); i++) {
            if (numIndexMap.find(nums[i]) != numIndexMap.end() && i - numIndexMap[nums[i]] <= k) {
                return true;
            } else {
                numIndexMap[nums[i]] = i;
            }
        }
        
        return false;
    }
};

                                            
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

                                            
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        num_dict = {}
        for i, num in enumerate(nums):
            if num in num_dict and abs(i - num_dict[num]) <= k:
                return True
            num_dict[num] = i
        return False

                                            
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    for(int i = 0; i < numsSize; i++) {
        for(int j = i+1; j < numsSize; j++) {
            if(nums[i] == nums[j] && abs(i - j) <= k) {
                return true;
            }
        }
    }
    return false;
}

                                            
public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        HashSet<int> set = new HashSet<int>();
        
        for (int i = 0; i < nums.Length; i++) {
            if (set.Contains(nums[i])) {
                return true;
            }
            
            set.Add(nums[i]);
            
            if (set.Count > k) {
                set.Remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */

const containsNearbyDuplicate = (nums, k) => {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i]) && (i - map.get(nums[i]) <= k)) {
            return true;
        }
        map.set(nums[i], i);
    }
    return false;
};

                                            
function containsNearbyDuplicate(nums: number[], k: number): boolean {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i]) && i - map.get(nums[i]) <= k) {
            return true;
        }
        map.set(nums[i], i);
    }
    
    return false;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Boolean
     */
    function containsNearbyDuplicate($nums, $k) {
        $map = array();
        
        for ($i = 0; $i < count($nums); $i++) {
            if (array_key_exists($nums[$i], $map) && $i - $map[$nums[$i]] <= $k) {
                return true;
            }
            $map[$nums[$i]] = $i;
        }
        
        return false;
    }
}

                                            
class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var numIndexMap = [Int: Int]()
        
        for i in 0..<nums.count {
            if let index = numIndexMap[nums[i]] {
                if i - index <= k {
                    return true
                }
            }
            numIndexMap[nums[i]] = i
        }
        
        return false
    }
}

                                            
class Solution {
    fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
        val map = HashMap<Int, Int>()
        
        for (i in nums.indices) {
            if (map.containsKey(nums[i]) && i - map[nums[i]]!! <= k) {
                return true
            } else {
                map[nums[i]] = i
            }
        }
        
        return false
    }
}

                                            
class Solution {
  bool containsNearbyDuplicate(List<int> nums, int k) {
    Map<int, int> map = {};
    
    for (int i = 0; i < nums.length; i++) {
      if (map.containsKey(nums[i]) && i - (map[nums[i]] ?? i) <= k) {
        return true;
      }
      map[nums[i]] = i;
    }
    
    return false;
  }
}

                                            
func containsNearbyDuplicate(nums []int, k int) bool {
    seen := make(map[int]int)
    
    for i, num := range nums {
        if j, ok := seen[num]; ok && i - j <= k {
            return true
        }
        
        seen[num] = i
    }
    
    return false
}

                                            
# @param {Integer[]} nums
# @param {Integer} k
# @return {Boolean}
def contains_nearby_duplicate(nums, k)
    seen = {}
    
    nums.each_with_index do |num, idx|
        if seen.key?(num) && idx - seen[num] <= k
            return true
        end
        seen[num] = idx
    end
    
    return false
end

                                            
impl Solution {
    pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
        use std::collections::HashMap;
        
        let mut num_map = HashMap::new();
        
        for (index, &num) in nums.iter().enumerate() {
            if let Some(&prev_index) = num_map.get(&num) {
                if (index as i32 - prev_index) <= k {
                    return true;
                }
            }
            
            num_map.insert(num, index as i32);
        }
        
        false
    }
}

To solve this coding challenge effectively, you need to determine if there are two distinct indices \(i\) and \(j\) in an array such that the values at these indices are equal and the absolute difference between \(i\) and \(j\) is at most \(k\). The challenge requires creating an efficient solution that can handle arrays of length up to \(10^5\) and values within a large range. Below are the steps and pseudocode to approach this challenge:

Explanation

Define the Problem: We need to check for a pair of indices \(i\) and \(j\) such that \( \text{nums}[i] = \text{nums}[j] \) and \( |i - j| \leq k \).
Hash Map Utilization: Utilize a hash map (dictionary) to store the last occurrence of each element in the array. This will allow quick lookups and efficient updates.
Iterate through Array: As we iterate through the array, check if the current element exists in the dictionary. If it does, check if the difference between the current index and the stored index for that element is less than or equal to \(k\).
Update Dictionary: Whether we find a valid pair or not, update the dictionary to set the current index as the last seen index for the current element.
Return Result: If a valid pair is found during the iteration, return true. If the iteration completes without finding a valid pair, return false.

Step-by-Step Explanation

Step-by-Step Explanation of the Pseudocode:

Initialization:

* Initialize an empty dictionary to store the last seen index of each element.

Iteration Through Array:

* For each element in the array, along with its index, check if the element is already present in the dictionary.

* If the element is present, verify if the difference between the current index and the stored index is less than or equal to \( k \).

* If the difference condition is satisfied, return true.

* Update the dictionary with the current index for the current element.

Return Result:

* If the loop completes without finding any valid pairs, return false.

Detailed Pseudocode:

Note: Make sure to include explanatory comments in the pseudocode.

                                            
# Function to determine if there are nearby duplicates in the array
function containsNearbyDuplicate(nums, k):
# Initialize an empty dictionary to store the last seen index of each number
last_seen_indices = {}

# Iterate through the array with index and value
for index, value in enumerate(nums):
# Check if the current number already exists in the dictionary
if value in last_seen_indices:
# Calculate the index difference between the current index and the last seen index
index_difference = index - last_seen_indices[value]

# Check if the index difference is less than or equal to k
if index_difference <= k:
return true  # Return true if the condition is satisfied

# Update the dictionary to store the current index for the current number
last_seen_indices[value] = index

# Return false if no such pair is found after iterating through the entire array
return false

Detailed Steps in Pseudocode:

Initialize the dictionary:

                                            
last_seen_indices = {}

* This dictionary will store the last index at which each element was found.

Iterate through the array with both index and value:

                                            
for index, value in enumerate(nums):

enumerate

provides both the index and value of elements in the array.

Check if the element exists in the dictionary:

                                            
if value in last_seen_indices:

* If the element is found in the dictionary, proceed to calculate the difference between indices.

Calculate the index difference and check condition:

                                            
index_difference = index - last_seen_indices[value]
if index_difference <= k:
return true

* If the difference is within

k

, return

true

as the condition is satisfied.

Update the dictionary:

                                            
last_seen_indices[value] = index

* Update or add the current index for the element in the dictionary.

Return false if no pairs are found after completing the iteration:

                                            
    return false

* This line concludes the function and returns

false

if no valid pairs have been found. By following these detailed steps and pseudocode, you can efficiently solve the problem within the constraints provided, ensuring that your solution is both clear and optimized for performance.