First leetcode Two Sum

Leetcode Submission

I ended up coding a crappy, brute force solution for this two sum problem in python. The question asks to return an array of two indicies whose values add together to a target value. Here’s their first example:

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

My solution in python is below. My thought was to keep a pointer and loop through the rest of the list. If the sum of the pointer’s value and the value currently being looped through is the target, add both indices to a solution list. We have two for loops to acheive this. In the worst case, the last two values are the ones which sum to the target. Therefore, we have to compare each value against every other value in the list. So, our runtime is O(n²). According to the site’s test, this took 3492 ms to run and 12.7 MB of memory.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        soln = []
        pointer = 0

        for number in nums:
            # store value of an index so that we can do our test
            # take the current index out of the list so that we can do test
            tmp_val = nums.pop(pointer)
            idx = 0

            for number in nums:
                if (tmp_val + number) == target:
                    soln.append(pointer)
                    soln.append(idx + 1)
                    return soln
                idx += 1
            
            nums.insert(pointer, tmp_val)
            pointer += 1

        return -1

To improve this, we can use some mathematic logic. If we have a target we can calculate what the number is needed if we keep our pointer. Then we only need to traverse the list once for O(n) time complexity and O(n) space complexity if we use a “map” or a dictionary in python. We keep track of the index and value that we’ve seen and ask if we’ve seen the value we need to get the sum. This is 2 ms and 13 MB memory.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        soln = []
        pairs = {}
        curr = 0

        for number in nums:
            x = target - number
            if (x in pairs):
                idx = pairs[x]
                soln.append(idx)
                soln.append(curr)
                return soln
            
            pairs[number] = curr
            
            curr += 1
        
        return -1