Takefumi Yamamura's blog

This blog is for my memorandum about programming and English.

Happy Coding

This blog is for my memorandum

Contains Duplicate III


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).