Python Solution Time Limit Exceeded: Contains Duplicate II


  • 0
    S
      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)?


  • 4
    P

    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

  • 0
    S

    Thank you! That's helpful!


  • 0
    N
    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

Log in to reply
 

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