You are given an integer array nums, and two integers k and t.

Your task:

Determine whether there exist two distinct indices i and j such that:

|i - j| ≤ k
AND
|nums[i] - nums[j]| ≤ t

Example:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Explanation: nums[0] and nums[3] differ by 0 and are within index distance 3

Another example:

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

---

Problem Understanding

This problem mixes value closeness and index closeness:

We need:

1. Values close enough: |nums[i] - nums[j]| ≤ t
2. Indices close enough: |i - j| ≤ k

Brute force would check all pairs within k distance for each index:

O(n * k) → too slow for large input

We need something faster.

---

Logic Explained in Simple English

Think about solving each constraint:

Constraint 1: indices within k

We only need to compare each element to the previous k elements.

So we maintain a sliding window of size at most k.

Constraint 2: values within t

Inside that sliding window, we need to know if there exists a number such that:

existing >= nums[i] - t  AND  existing <= nums[i] + t

This means:

We need a data structure that can:

• store numbers in sorted order
• search for nearest value
• run in O(log n)

Best option in Java:

TreeSet

Strategy:

1. Iterate through nums
2. For each number:
   • search TreeSet for smallest number ≥ nums[i] – t
   • if that number exists and ≤ nums[i] + t → return true
3. Add nums[i] to TreeSet
4. If TreeSet size exceeds k → remove nums[i-k]

Why this works:

• TreeSet always contains at most k previous values
• Searching for ceiling gives potential neighbors
• Fast enough: O(n log k)

---

Step-by-Step Approach

1. Create a TreeSet<Long>
2. Loop i from 0 to nums.length-1
3. For each nums[i]:
   • Let targetLow = nums[i] – t
   • Find candidate = ceiling(targetLow)
   • If candidate exists and candidate ≤ nums[i] + t → return true
4. Add nums[i] to TreeSet
5. If TreeSet size > k → remove nums[i-k]
6. If loop finishes, return false

Use long arithmetic to avoid overflow.

---

Java Implementation

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k <= 0 || t < 0) return false;

        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            long val = nums[i];

            Long candidate = set.ceiling(val - t);
            if (candidate != null && candidate <= val + t) {
                return true;
            }

            set.add(val);

            if (set.size() > k) {
                set.remove((long) nums[i - k]);
            }
        }

        return false;
    }
}

---

Dry Run Example

Input:

nums = [1,2,3,1], k = 3, t = 0

TreeSet starts empty.

i = 0 → val = 1
candidate = ceiling(1) → null
add 1
set = {1}

i = 1 → val = 2
candidate = ceiling(2) → null
add 2
set = {1,2}

i = 2 → val = 3
candidate = ceiling(3) → null
add 3
set = {1,2,3}

i = 3 → val = 1
candidate = ceiling(1) → 1
check 1 ≤ 1 → TRUE

Return true

---

Time and Space Complexity

Time Complexity

O(n log k)

TreeSet operations cost log k, and there are n insertions/searches.

Space Complexity

O(k)

TreeSet holds at most k elements.

---

Common Mistakes and How to Avoid Them

Mistake 1: Using absolute differences directly

This risks overflow:

|nums[i] - nums[j]|

Use long arithmetic.

Mistake 2: Forgetting to remove old elements

Otherwise index constraint fails.

Mistake 3: Using HashSet instead of TreeSet

HashSet cannot do range searches.

Mistake 4: Misinterpreting inequality direction

Must use:

candidate ≥ val - t
AND
candidate ≤ val + t

Mistake 5: Assuming sorted array logic applies

Array order matters due to index constraint.