Reference: LeetCode
Difficulty: Medium

## Problem

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example:

## Analysis

### Tree Set

Based on the solution in Contains Duplicate II, we use a tree set to keep k elements in ascending order.

Then we find the closest elements of nums[i]. We do binary search for value nums[i] to find the floor and ceiling elements, and compare them with nums[i] to see if the requirement is satisfied.

Note:

• At the beginning, the tree set is empty.
• Use Long type to solve the overflow problem.

Time: $O(N\log{(\min(N, k))})$
Space: $O(\min(N, k))$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.