LeetCode Problem 1. Two Sum Solution in Python

This is a solution for the coding problem 1. Two Sum from LeetCode in Python:

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.

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

Only one valid answer exists.

Solution:

Have you ever played a game where you have to add up two numbers to get a certain target number? Well, that’s kind of like the problem we’re going to talk about today.

Imagine you have a list of numbers and you want to find which two numbers in the list add up to a certain target number. How would you do it?

One way is to check every single combination of numbers and see if they add up to the target. But that would take a long time, especially if you have a really big list of numbers. Can you think of a faster way?

The code we have here is a solution that can help us find the right two numbers really quickly. It does this by using something called a “dictionary”. A dictionary is like a special list that can store values and their locations (called “indices”) in the list.

Here’s how the code works:

First, it creates an empty dictionary called “hashMap”. Then it loops through every single number in the list. For each number, it calculates the difference between the target number and the current number.

Then it checks if that difference is already in the dictionary. If it is, that means we’ve already seen a number that, when added to the current number, would give us the target number. So the code returns the indices of those two numbers and we’re done!

If the difference isn’t in the dictionary, the code adds the current number and its index to the dictionary. This way, if we see the number that would give us the target sum when added to the current number later on, we can quickly find its index using the dictionary.

Once the code has looked at every single number in the list, it checks if it found a solution. If it didn’t, it returns an empty list.

This solution is really fast because it only has to loop through the list of numbers once. That’s called “linear time” complexity, and it’s usually a lot faster than other ways of solving problems. It also doesn’t use up a lot of extra space, because it only stores the values and indices it needs in the dictionary.

Here is the complete code:

class Solution(object):
    def twoSum(self, nums, target):
        """
        Finds the indices of the two numbers in the given list that add up to the target.
        :param nums: List[int] - list of integers
        :param target: int - target sum
        :return: List[int] - list of indices of the two numbers
        """
        
        # create an empty dictionary called "hashMap" to store the values and indices of the numbers we've seen
        hashMap = {}
        
        # loop through all the elements in the list of numbers
        for i in range(len(nums)):
            # calculate the difference between the target and the current element
            diff = target - nums[i]
            
            # check if the difference is already in the dictionary
            if diff in hashMap:
                # if it is, return the indices of the current element and the element with the matching difference
                return [hashMap[diff], i]
            else:
                # if it's not, add the current element and its index to the dictionary
                hashMap[nums[i]] = i
        
        # if the loop finishes running and we haven't found a solution, return an empty list
        return []

Let’s walk through an example to see how this code works.

Suppose we have the following list of numbers: [2, 7, 11, 15] and the target sum is 9.

Here’s what the code does:

1. It creates an empty dictionary called “hashMap”.
2. It starts a loop that will go through each number in the list. The loop counter is called “i”.
3. The first time through the loop, “i” is 0 and the current number is 2. The code calculates the difference between 9 and 2, which is 7. 7 is not in the dictionary, so the code adds the current number (2) and its index (0) to the dictionary. The dictionary now looks like this: {2: 0}
4. The loop moves on to the next number. “i” becomes 1 and the current number is 7. The code calculates the difference between 9 and 7, which is 2. 2 is in the dictionary, so the code returns the indices of the current element (1) and the element with the matching difference (0). The indices are [0, 1] and that’s the answer we’re looking for.

Time complexity: The code only loops through the list of numbers once, so its time complexity is O(n), where “n” is the size of the list. This is considered very fast, especially compared to other ways of solving this problem that might involve nested loops or sorting the list, which would take much longer.

Space complexity: The code only uses a single dictionary to store the values and indices of the numbers we’ve seen, so its space complexity is O(n). This is also considered very efficient, because the space used by the code doesn’t grow very quickly as the size of the input grows.

I hope this helps clarify how the code works and why it’s a good solution to the problem! Let me know if you have any questions.