Grind 75 Questions - 1 - Two Sum

Introduction:

Based on the "Grind 75", I will solve the 75 different problems on LeetCode, all using Python. I will follow the below format for all problems.

The Grind75 is

The first problem is Two Sum. Let's dive in.

Two Sum:

1. Problem Statement (LeetCode 1: Two Sum, Difficulty: Easy):
2. 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.
3. For example:

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

1. Questions to Ask the Interviewer:

• ?? Are the numbers in the array sorted?
• ?? Can the array contain negative numbers?
• ?? Can the array contain duplicate numbers?
• ?? What should the function return if no solution is found?

2. Edge Cases:

?? What if the array is empty?

?? What if the array only has one element?

?? What if the array has duplicate elements that sum up to the target?

3. Available Approaches:

Brute Force Approach:

You can use two loops. In the outer loop, take one element, and in the inner loop, check for the other number, which, when added to the first one, equals the target.

def two_sum(nums, target):
? ? # Loop through each number in the list.
? ? for i in range(len(nums)):
? ? ? ? # Loop through the rest of the numbers in the list.
? ? ? ? for j in range(i + 1, len(nums)):
? ? ? ? ? ? # If these two numbers add up to the target,
? ? ? ? ? ? if nums[i] + nums[j] == target:
? ? ? ? ? ? ? ? # return their indices.
? ? ? ? ? ? ? ? return [i, j]
? ? # If no two numbers sum up to the target, return an empty list.
? ? return []

        

In this code, we start with the first number (nums[i]), then check every other number in the list (nums[j]) to see if they add up to the target. If they do, we return their indices. If we've checked all pairs of numbers and haven't found a pair that adds up to the target, we return an empty list.

Note that this approach has a time complexity of O(n^2), where n is the number of elements in the list, because for each element in the list, we're checking every other element. This is less efficient than the dictionary-based approach, which only needs to check each element once, resulting in a time complexity of O(n). However, the brute force approach is simpler and doesn't require any additional space, which could make it a reasonable choice for smaller inputs.

Hashing (Efficient Approach):

You can use a dictionary to store the number as a key and its index as a value. Then for each number, you check if its complement (target - number) exists in the dictionary or not. If it does, return the indices.

def two_sum(nums, target):
? ? num_map = {}? # Create a dictionary to store the numbers and their indices.
? ??
? ? # Iterate through the list of numbers.
? ? for i, num in enumerate(nums):
? ? ? ? # Calculate the complement of the current number.
? ? ? ? complement = target - num


? ? ? ? # If the complement exists in our map, return the index of the complement and the current index.
? ? ? ? if complement in num_map:
? ? ? ? ? ? return [num_map[complement], i]


? ? ? ? # If the complement does not exist in our map, add the current number and its index to the map.
? ? ? ? num_map[num] = i


? ? # If no two numbers sum up to the target, return an empty list.
? ? return []

        

Logic Explanation:

• Imagine you are given a list of numbers and a target number, and you need to find two numbers from the list that add up to this target.
• What we do is start at the beginning of the list and for each number, we calculate what we'd need to add to it to reach the target. This is called the complement.
• We then check if we have encountered this complement before while traversing the list. If yes, that means we have found our pair of numbers that add up to the target.
• If not, we remember this number and where we found it (its position in the list) and then move on to the next number in the list.
• We keep doing this until we have gone through the entire list. If we do find a pair that adds up to the target, we return their positions. If not, we return an empty list indicating that no such pair exists.

Code Explanation:

• We create a dictionary called num_map to remember the numbers and their positions in the list. A dictionary is a data structure that lets us store pairs of information together - in this case, a number from the list and its position in the list.
• We then start looking at each number in the list. For each number, we calculate what we would need to add to it to reach the target. This is the complement.
• We check if this complement is already in our dictionary. If it is, we have found our pair of numbers that add up to the target. We return the position of the complement from the dictionary and the current position.
• If the complement is not in our dictionary, we add the current number and its position to the dictionary.
• We do this for every number in the list. If we have gone through the entire list and haven't found a pair, we return an empty list.

Pattern:

The pattern in this problem is that for each number in the list, we are trying to find its complement in the rest of the list. If we find it, we know that these two numbers add up to the target. By storing the numbers and their indices in a dictionary, we can quickly look up the complement. This is a typical pattern in problems where we need to find pairs of elements that satisfy some condition. It shows the power of the dictionary data structure for lookup operations.

Big O Notation Explanation:

For the given problem, the time complexity of our solution is O(n), where n is the size of the input list. This means that in the worst-case scenario, our algorithm will perform a number of operations that is proportional to the size of the list. This is because we iterate over the list just once, performing constant time operations for each element.

The space complexity of the algorithm is also O(n), as in the worst-case, we might end up storing every element of the list in the dictionary.

Points to Remember:

• Using a data structure to keep track of seen elements (in this case, a dictionary in Python) can be very helpful.
• By storing the complement of the number (i.e., target - current number), we can solve the problem in one pass through the list.
• Remember to handle the case where no valid pair exists.

Testing with sample data:

nums = [2, 7, 11, 15], target = 9

1. We start by creating an empty dictionary num_map.
2. We then start a loop over the list nums, considering both the index i and the number num at that index.
3. For each num, we calculate its complement which is target - num. For the first number in our list (nums[0] = 2), the complement would be 9 - 2 = 7.
4. We check if this complement is in our num_map. Initially, the num_map is empty, so the complement (7) will not be found.
5. As the complement is not found, we add the current num and its index i to the num_map. Now, num_map becomes {2: 0}.
6. We then move on to the next number in the list. num becomes 7 and i becomes 1. The complement here is 9 - 7 = 2.
7. Now when we check if the complement (2) is in our num_map, we find it is (num_map is {2: 0}). This means that we have found two numbers that add up to our target (nums[0] which is 2, and nums[1] which is 7).
8. We then return the indices of these two numbers, which are [num_map[complement], i], or [0, 1] in this case.

If we didn't find any two numbers that add up to the target after going through the entire list, we would return an empty list [].

This solution is faster than the brute force approach because we're only going through the list once; hence it has a time complexity of O(n). We're using a dictionary to remember the numbers we've seen and where we saw them, which makes checking if we've seen a number before very fast (in constant time, O(1)).

The next problem will be Valid Parentheses(Stacks).