# A C# O(NLogK) Solution by using SortedSet

• EDIT: Fix it by using SortedSet.GetViewBetween

``````public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(t < 0) return false;
SortedSet<long> ss = new SortedSet<long>();
for(int i = 0; i < nums.Length; i++){
if(ss.GetViewBetween((long)nums[i] - t, (long)nums[i] + t).Count > 0) return true;
if(i >= k) ss.Remove(nums[i - k]);
}
return false;
}
``````

Below is the old version of O(Log(N*K))

``````public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
SortedList<int, int> sdc = new SortedList<int, int>();
for (int i = 0; i < nums.Length && k != 0; i++){
for (int j = 0, l = sdc.Count - 1; j <= l;)
if ((long)nums[i] - (long)sdc.Keys[(j + l) / 2]  > (long)t)
l = (j + l) / 2 - 1;
else if ((long)nums[i] - (long)sdc.Keys[(j + l) / 2] < -(long)t)
j = (j + l) / 2 + 1;
else return true;
if (sdc.Count == k)
sdc.RemoveAt(sdc.IndexOfValue(i - k));
}
return false;
}``````

• Looks like O(n^2) to me. Add and RemoveAt are expensive.

• remove and add is at O(n) level.
still thinking how to maintain a K-length window effectively
C# doesn't have treeset. I don't want to use linq built-in queries too..

• inner loop is a binary search

• I'm confused. Your title still says O(N*LogK). Do you not think that it's O(n^2) or at least O(nk)?

• I don't think it's N*K. the Inner loop is a binary search in a K-Window so it's LogK

• Yes, yes, the binary search is fast. Which is why I didn't even mention it. What I did say is "Add and RemoveAt are expensive". They're linear time. And you do them (up to) N times. So you have "linear times linear".

• Btw, can `sdc.ContainsKey(nums[i])` ever be true? Wouldn't the binary search have succeeded and the function returned?

• you are right. I removed that part.

• Understand. trying to figure out workaround

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.