Contains Duplicate III 🚧

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 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Incorrect Attempt

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        //if (k == 0) return true;
        if (k >= nums.size() || nums.size() == 0 || k <= 0 ) return false;

        int a = 0;
        int b = a + k;

        for (; b < nums.size(); a++, b++) {
            if ((abs(nums[a] - nums[b])) <= t) return true;
        }
        return false;
    }
};

This fails for input

[2,2]
3
0

Also, the discussions involve more elaborate solutions. So this naive solution is incorrect.

Understand the problem

I was missing a key point in the problem. The words “at most“. That changes the problem! 😮

We need to think of a dynamic sliding window that goes from length 1 to length k.

Let’s check an example:

Given Input: nums = [1,2,3,1], k = 3, t = 0

Here the max window length is 3 and thus 1 - 1 satisfies the condition.

Let’s see another example where the answer where the result is true.

[12,14,15]
1
1

This is because 15 - 14 satisfies within the given window of 1.

And k can exceed the size of your given vector! So the below one also results in true.

[12,14,15]
11
1

Now for this example we expect a false because the max window size is 2 and the max difference we can accept is 5. Which is only possible for 15 - 10 or 104 - 100 here.

[112,104,15,60,100,1,10]
2
5

Increasing window size (k) to 3 results in true.

Analysis

The brute-force approach would be to try every pair until we find one that works for the given constraints. But then we end up visiting the same pairs of indices many times. It would be a good idea to cache them somehow.

Accepted

After scouring the discussion over a few days I think I have pieced the logic together.

The idea is that we use a set to represent a sliding window.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> window; // set is ordered automatically
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
            auto pos = window.lower_bound((long)nums[i] - t);
            if (pos != window.end() && abs(*pos - (long)nums[i]) <= t) return true;
            window.insert(nums[i]);
        }
        return false;
    }
};

Explained

|a -b| <= t
implies
(a - b) <= t
or (b - a) <= t

If a and t are known then we can search for a number equal to or just greater than (a - t).
If found then we can test it to see if satisfies the given constraint of |a - b| <= t.

Side note about std::set

C++ provides an API for the set which allows us to find the number equal to or next greatest than given value.

// set::lower_bound/upper_bound
#include <iostream>
#include <set>
using namespace std;

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator itlow,itup;

  for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

  itlow=myset.lower_bound(1200);                //       ^
  if (itlow != myset.end()) cout << "lower = " << *itlow << endl;
  itlow=myset.lower_bound(5);                //       ^
  if (itlow != myset.end()) cout << "lower = " << *itlow << endl;
  itup=myset.upper_bound (65);                 //                   ^
  cout << "upper = " << *itup << endl;
  myset.erase(itlow,itup);                     // 10 20 70 80 90

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Results in:

lower = 10
upper = 70
myset contains: 70 80 90

Explore here