LeetCode 1 – Python 3 (Week 1 – 01)

Solution 1 (Runtime: 1288 ms Memory Usage: 14.6 MB)

class Solution:
     def twoSum(self, nums: List[int], target: int) -> List[int]:
      
     for i in nums:
        j = target - i
        indice_1 = nums.index(i)
        indice_2 = indice_1 + 1
        tmp_nums = nums[indice_2: ] # you may not use the same element twice
        if j in tmp_nums:
            return(indice_1, tmp_nums.index(j)+indice_2) # not use nums.index(j) because 'you may not use the same element twice'

Solution 2 (Runtime: 60 ms Memory Usage: 15.2 MB)

class Solution:
     def twoSum(self, nums: List[int], target: int) -> List[int]:

     numspool = {} #dictionary

     for i in range(len(nums)):
        if target - nums[i] not in numspool:
            numspool[nums[i]] = i
        else:
            return(numspool[target - nums[i]], i)

Time complexity of solution 1 is O(n*n). Time complexity of solution 2 is O(n). Because dictionary offer O(1) lookup time. Space complexities of both of them are O(n).

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create your website at WordPress.com
Get started
%d bloggers like this: