# September LeetCoding Challenge, Day 2: Contains Duplicate III

September 3, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

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