Two Sum | LeetCode 1 | Python | Solution

LeetCode 1

Read the problem description first and think about the problem.

We will be given an integer array and target. Target is also an integer. We have to find two elements out from the given array, where the sum of those two elements has to be equal to the target. After that, we will return the index of those two elements as an array. Ordering does not matter.

array = [1, 2, 3, 4, 5], target = 9
[1, 2, 3, 4, 5] -> [3, 4]

As per the problem description, the input array contains exactly one solution, and we are not allowed to use the same element twice.

Let’s think about a brute-force solution that can come to mind first. Start to check the first element of the given array with the rest of the arrays element one by one. Then check the second element with the rest. But this time, we don’t need to check the first element. We can ignore it because we already did it. We only need to check the right portion. We will continue to do it until we find the result.

Let’s see the code for better understanding.

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

But the time complexity of this solution is O(N^2). We can come up with a more optimal solution than this. And the problem description also wants a better solution than the O(N^2). So let’s see.

Another way we can solve this problem is by using HashTable. In this HashTable, we will store the remaining value as a key after subtracting an element from the target, and the index of that element will be the value of that key. And We will be doing it from start to end until we get the answer. That means if any of the elements match with the stored key, we will get our result.

We don’t need to worry much, because there is only one answer. Let’s see a demo.

array = [2, 5], target = 7

1st Iteration
index = 0
2 is not in table
7 - 2 = 5
table = {5: 0}

2nd Iteration - 
index = 1
5 is in table
So, result will be = [table[5], index]
[0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        table = {}
        
        for i, num in enumerate(nums):
            
            if num in table:
                return [table[num], i]

            remain = target - num
            table[remain] = i

The time complexity of this solution is O(N), which is a pretty better solution than the previous one. We all know that the time complexity of the HashTable data structure’s operations is O(1).

I hope you got the idea about the problem and the solution.
Happy Learning.
Happy Coding.