# September LeetCoding Challenge, Day 2: Contains Duplicate III

September 3, 2020The problem for September 2 is Contains Duplicate III. The title of
the problem is a bit misleading, since the statement isn’t about finding
duplicates. Instead, we’re interested in finding, from an array of numbers
`nums`

and integers `k`

and `t`

, whether there are two distinct indices `i`

and
`j`

such that the absolute difference of `nums[i]`

and `nums[j]`

is at most `t`

and the absolute difference between `i`

and `j`

is at most `k`

.

One way to approach this problem is to, for each number in the array, check if
there is a number in the previous `k`

numbers such that the absolute difference
between them is at most `k`

. If we can keep a sorted list of `k`

numbers at all
times, we should be able to do this in \(\mathcal{O}(n \times log(k))\), \(n\)
being the size of the `nums`

array. The \(\mathcal{O}(n)\) part is due to the
fact that we have to iterate through all elements of `nums`

. The
\(\mathcal{O}(log(k))\) part is due to the fact that, if we can keep a sorted
list of the previous `k`

numbers, we can binary search for the element that
minimizes the absolute difference. A way to implement this in C++ is to use a
`multiset`

(a simple `set`

doesn’t work since there can be repeated elements in
`nums`

). Elements in C++
`multisets`

are sorted and
the interface provides both `lower_bound`

and `upper_bound`

methods to search
for elements in logarithmic time complexity. The following is an implementation
of that strategy:

We check two numbers in each iteration: the number returned by the `lower_bound`

method (which is going to be the first number that is larger than or equal to
`nums[i]`

) and the number immediately before (the larger number that is smaller
than `nums[i]`

). One of those is going to be the one producing the smallest
absolute difference. If the smallest absolute difference is not greater than
`t`

, we have found a satisfying pair.

The casts to `long long`

are necessary because, even though `t`

is an `int`

, the
absolute difference between two numbers in `nums`

may not fit in an `int`

(consider \(|2147483647 - (-2147483648)|\) for example).