# Python without dictionary

• ``````class Solution:
# @param {integer[]} nums
# @param {integer} k
# @param {integer} t
# @return {boolean}
def containsNearbyAlmostDuplicate(self, nums, k, t):
ind = sorted(range(len(nums)), key = lambda x: nums[x])
for i in range(len(nums)-1):
j = i + 1
while j < len(nums) and nums[ind[j]] - nums[ind[i]] <= t:
if abs(ind[i]-ind[j]) <= k:
return True
j += 1
return False
``````

ind is an array of the indexes of sorted num. Iterate through ind to check if nums are within t and ind are within k.

• intuitively solution, nice~

• This algorithm's time complexity seems to be O(n^2), why it didn't cause time limit exceed in OJ?

• I think the time complexity of this method is not `O(n^2)`. It should be `O(n*t)`, as the while loop will have `t` comparisons at most. The brutal-force solution which searches each k-sized bucket is `O(n*k^k)`. So it depends on the values of `t` and `k^k` when comparing which one is better.

• Yes you are right, later I figured it out. Since it's called Contain Duplicate III, the `t` should be a relatively small number :)

• @caikehe I thought it should be `O(n*t)` vs `O(n*k)`, because in these family of solutions position / k and num / t are interchangeable.

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