Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Contains Duplicate III

LeetCode binary search tree

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.

how to solve

To solve this problem, I use set(binary search tree). In set, the value is sorted automatically and I can insert and delete in O(logn). We can check the most near higher element and the most near lower element in O(logn) using lower_bound. So we can get answer in O(nlogn).

code