I believe that every software developer who has heard of Leetcode must also heard of Two Sum, because this is the very first problem in Leetcode website. Even though it is in easy difficulty, it is still worth mentioning and being written down here. And next time, I will move on to the very first Leetcode medium question!

Question: Two Sum

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.

Examples:

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

Constraints:

2 <= nums.length <= 10``4
10``9 <= nums[i] <= 10``9
10``9 <= target <= 10``9

Only one valid answer exists.

Thought process

Brute force - O(n²)

For the brute force method, we simply iterate through the array twice, checking each pair of elements to see if they add up to the target value. This method has a time complexity of O(n²), which is easy to think of, but not very efficient.

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]

Hash map - O(n)

In the hash map approach, we iterate through the array once and store each element in a hash map along with its index. Then, for each element, we check if the difference between the target and the current element exists in the hash map. If it does, we have found the pair of elements that add up to the target and return their indices. Otherwise, we add the current element and its index to the hash map and continue iterating through the array.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashMap = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in hashMap:
            j = hashMap[diff]
            return [i, j]
        else:
            hashMap[num] = i

Summary

In summary, the Two Sum problem is a classic interview question that tests a candidate's ability to think creatively about problem solving. The brute force method is a simple solution but not very efficient, while the hash map approach is much faster and more scalable. As a software developer, it is important to be familiar with both approaches and to be able to choose the appropriate one for a given problem.