Leetcode 1: Two Sum

Problem Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Thought Process

First I thought about having 2 nested loops to check each pair of numbers in the array. However, this would be O(n^2) time complexity which is not optimal. Instead, I can use a hash map to store the indices of the numbers as I iterate through the array. This way, I can check if the remainder (target - current number) exists in the hash map in O(1) time. If it does, I can return the indices of the current number and the number in the hash map. If it doesn’t, I can add the current number and its index to the hash map.

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen={nums[0]:0}
        for i,num in enumerate(nums[1:]):
            remainder=target-num
            val=seen.get(remainder,None)
            if not val is None:
                return [val,i+1]
            seen[num]=i+1
        return []

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n) where n is the number of elements in the array. This is because we are iterating through the array once and performing amordized O(1) operations for each element.

Space Complexity

The space complexity is O(n) since we are using a hash map to store the indices of the numbers. In the worst case, we may have to store all n elements in the hash map.

Difficulty

This problem is considered easy on Leetcode. However I didn’t think it was as easy as other easy problems there, at least when it comes to writing optimal code. It is easy to write the brute force solution but I think it is a good exercise to think about how to optimize it. I also think that the hash map solution is a good example of how to use data structures to solve problems efficiently.