I have taken a few days off from the grind. I’ve been looking at purchasing my first home 🏡.

Today’s leetcode problem. We are given an array of integers nums, and an integer target. We need to return the indices of two numbers such that they add up to target. The constraints say that there will always be one valid answer in the given integer array.

My first thought is to use a nested for loop to starting iterating from index 0, and a secondary iterator to go down the list.

The diagram below will start with index i set to 0. A secondary iterator j will traverse down the rest of the list. At each iteration, it will compare the addition result of i + j and see if it equals to target. If it does, then we can return a tuple of (i,j). If we still have not found the match, then we can increment i and repeat the process.

t 1 a s r t 2 g 2 i n 2 e i d t t = e i 9 r ( t a i e t j 7 t r 7 i i e a o r t n a i ( t o ( i o n i t 1 r 1 t e 1 ( j 1 e r i a r a ) n a t d t o ( o r s i r 1 o t 1 j 5 e 5 i ) o r ) n a . t . o . r . ) j )

Here is the code solution:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

My answer was accepted, however I’m aware it’s runtime is not going to be good. The runtime is poor as it has to do a lot of looping with the J iterator. My runtime was 16.57% faster than the majority of submissions. Not very great. My memory usage statistic was less that 99.63% of submissions.

Optimizing⌗

My method was brute force, which is not ideal in any circumstance, but it’s a good fallback option during interviews when you may get stumped. A little bit of research showed that I could have utilized a hashmap to improve the runtime speed.

class Solution:
    def twoSum(nums: List[int], target: int) -> List[int]:
        # List to store results
        result = []
        # Dictionary to store the difference and its index
        index_map = {}
        # Loop for each element
        for i, n in enumerate(nums):
            # Difference which needs to be checked
            difference = target - n
            if difference in index_map:
                result.append(i)
                result.append(index_map[difference])
                break
            else:
                index_map[n] = i
        return result