I can't believe my python hash table implementation timed out


  • 0
    B
    class Solution(object):
        def twoSum(self, nums, target):
    		dict = {}
    		for i, v in enumerate(nums):
    			dict[v] = i+1
    		
    		for v in nums:
    			if target-v in dict.keys() and dict[target-v] != dict[v]:
    				return [dict[v], dict[target-v]]
    

    This is O(n) implementation. Is there anything else I can optimize in reduce run time?


  • 1
    B

    The problem is that the unsorted array will take O(n^2) to look for target-v in dict.

      def twoSum(self, nums, target):
    		nums_sorted = sorted(nums[:])
    		dict = {}
    		for i, v in enumerate(nums_sorted):
    			dict[v] = i+1
    			
    		for v in nums_sorted:
    			if target-v in dict.keys():
    				first_index = nums.index(v)
    				second_index = nums.index(target-v)
    				if dict[v] == dict[target-v]:
    					second_index += 1
    					while nums[second_index] != nums[first_index]:
    						second_index += 1
    				return sorted([first_index+1, second_index+1])

Log in to reply
 

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