NUHMAN.com

🧩 Problem Statement

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 |i - j| <= k.

📘 Example

go

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

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

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

🧠 Approach

To solve this problem, we can use the sliding window technique combined with a hash map.

Key Idea:

• We need to check if there are duplicate values in the array, but only within a window of size k.
• We can use a hash map (or dictionary) to store the indices of elements we’ve seen so far.
• As we iterate through the array, if an element appears again, we check if the difference between its current index and the previous index is ≤ k.

Steps:

1. Use a hash map to store the element's index as you iterate through the array.
2. If the element has already been seen in the map, check if the difference between the current index and the stored index is ≤ k.
3. If such a pair exists, return true. If no such pair is found after processing the entire array, return false.

✅ Go Implementation

go

package main

import "fmt"

func containsNearbyDuplicate(nums []int, k int) bool {
    // Map to store the index of each element
    indexMap := make(map[int]int)

    // Iterate through the array
    for i, num := range nums {
        // If the number has appeared before, check the index difference
        if prevIndex, found := indexMap[num]; found {
            if i-prevIndex <= k {
                return true
            }
        }
        // Update the map with the current index of the number
        indexMap[num] = i
    }

    return false
}

func main() {
    // Test cases
    fmt.Println(containsNearbyDuplicate([]int{1, 2, 3, 1}, 3)) // Output: true
    fmt.Println(containsNearbyDuplicate([]int{1, 0, 1, 1}, 1)) // Output: true
    fmt.Println(containsNearbyDuplicate([]int{1, 2, 3, 1, 2, 3}, 2)) // Output: false
}

📦 Example Usage

go

func main() {
    fmt.Println(containsNearbyDuplicate([]int{1, 2, 3, 1}, 3)) // Output: true
    fmt.Println(containsNearbyDuplicate([]int{1, 0, 1, 1}, 1)) // Output: true
    fmt.Println(containsNearbyDuplicate([]int{1, 2, 3, 1, 2, 3}, 2)) // Output: false
}

⏱️ Time & Space Complexity

• Time Complexity: O(n), where n is the number of elements in nums. We traverse the list once, and each map operation (insertion and lookup) takes O(1) on average.
• Space Complexity: O(n), for storing the indices in the hash map, where n is the number of unique elements in nums.

This approach ensures that we only use a sliding window of size k and efficiently check for duplicate values within that window.