0220.Contains-Duplicate-III code is incorrect

[lhfelis]

Sample code can't AC in leetcode, broken in case "[1,2,1,1] 1 0". The code only compares edge points(i, j), it should compare the newly added arr[j] with all the items within range [i, j-1]. To do this fast enough, something like BST may help to achieve log(n) find and update.

for j < len(elemList) {
	// Need to compare j with the closest value within range [i, j-1]
	if elemList[j].val-elemList[i].val <= t {
		if abs(elemList[j].idx-elemList[i].idx) <= k {
			return true
		}
		j++
	} else {
		i++
		if j <= i {
			j++
		}
	}
}

[halfrost]

@lhfelis Thank you for pointing out this error logic in my solution.

I did submit this code, getting AC a year ago (Link: https://leetcode.com/submissions/detail/245618353/). I think LeetCode has changed some test data. I rewrote the solution and did it using bucket sorting. Time complexity O(n), space complexity O(min(n,k))

Code in there

[lhfelis]

Great!