NUHMAN.com

🧩 Problem Statement

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that:

• |nums[i] - nums[j]| <= t
• |i - j| <= k

If no such pair exists, return false.

📘 Example

go

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

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

🧠 Approach

To solve this problem, we can use the sliding window technique with bucket sorting. This is a more efficient approach than brute-force, which would take O(n²) time.

Key Idea:

• We need to check if there are two numbers that satisfy:
• Their absolute difference is less than or equal to t.
• Their indices' difference is less than or equal to k.
• We can divide the numbers into "buckets" based on the value of t, and then check each bucket for possible duplicates.
• For each number in the array, if we can find a valid pair within the window (considering both index difference and value difference), we return true. Otherwise, after processing all numbers, return false.

Steps:

1. For each element nums[i], create a bucket for the number, where the bucket size is t + 1. This allows us to check if two elements are close enough in value.
2. If a number is found in the same bucket or in an adjacent bucket, check if the condition |nums[i] - nums[j]| <= t holds true.
3. If no such pair exists, return false. If a valid pair is found, return true.

✅ Go Implementation

go

package main

import "fmt"

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    // Edge case: If k or t are negative, return false
    if k <= 0 || t < 0 {
        return false
    }

    // Map to store the buckets
    bucket := make(map[int]int)

    // Helper function to get the bucket index for a number
    getBucketIndex := func(num int) int {
        if num < 0 {
            return (num + 1) / (t + 1) - 1
        }
        return num / (t + 1)
    }

    // Iterate through the numbers
    for i, num := range nums {
        bucketIndex := getBucketIndex(num)

        // Check the current bucket for the same value
        if val, exists := bucket[bucketIndex]; exists {
            if abs(num-val) <= t {
                return true
            }
        }

        // Check the adjacent buckets
        if val, exists := bucket[bucketIndex-1]; exists && abs(num-val) <= t {
            return true
        }
        if val, exists := bucket[bucketIndex+1]; exists && abs(num-val) <= t {
            return true
        }

        // Add the current number to its bucket
        bucket[bucketIndex] = num

        // If the window size exceeds k, remove the element at index i-k
        if i >= k {
            delete(bucket, getBucketIndex(nums[i-k]))
        }
    }

    return false
}

// Helper function to calculate absolute value
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

📦 Example Usage

go

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

⏱️ Time & Space Complexity

• Time Complexity: O(n), where n is the number of elements in nums. We process each element once, and each bucket operation (insert or lookup) takes O(1) on average.
• Space Complexity: O(n), for storing the elements in the bucket map, where n is the number of unique elements in nums.

This approach is more efficient than brute force because it reduces the problem to checking adjacent elements using a bucket-based technique, allowing us to process the list in linear time.