# Python Solution Time Limit Exceeded: Contains Duplicate II

• ``````  def containsNearbyDuplicate(self, nums, k):
final_list = []
temp_list = []
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j] and abs(i - j) <= k:
temp_list = [i, j]
final_list.append(temp_list)
if final_list:
return True
else:
return False
``````

### I am new here and wondering if all the code submitted in Leetcode need to be O(n^2)?

• Time limit exceeded might be because the solution you have is O(n^2) (though minor improvements can be done to yours). This problem could be solved in O(n) run time complexity using a dictionary for lookup. For instance, the code could be:

``````def containsNearbyDuplicate(self, nums, k):
n = len(nums)
if n == 0:
return False
d = {}
for i in range(n):
if nums[i] not in d:
d[nums[i]] = i
else:
diff = abs(d[nums[i]]-i)
if diff <= k:
return True
else:
d[nums[i]] = i
return False``````

• ``````class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {boolean}
def containsNearbyDuplicate(self, nums, k):
if len(nums) == 0:
return False
nums_dic = dict()
for position in range(0, len(nums)):
if nums[position] in nums_dic and position - nums_dic[nums[position]] <= k:
return True
nums_dic[nums[position]] = position
return False``````

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