Question: https://leetcode.com/problems/two-sum/description/

So, first I solved it with a basic approach of two loops. O(n^2).

class Solution:
    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]

Then I tried sorting (Like I did yesterday) and then comparing but did a mistake.

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

But that also didn’t work out. because if the array is 3,2,4 then when you sort it it becomes 2,3,4 .

It has a pair that returns 6 but wouldn’t give answer as 2 and 4 are never paired together.

Then, I tried two pointer. It successfully provides the pairs but not the correct indices.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i=0
        j=len(nums)-1
        while i<j:
            if((nums[i]+nums[j]) == target):
                return [i,j]
            elif((nums[i]+nums[j]) > target):
                j=j-1
            else:
                i+=1

Why? Well, if the array is 3,2,4 then when you sort it it becomes 2,3,4 the two pointer gives indices [] in output. But the correct answer is [1,2]

So, what else could be done?

I would be honest I needed to look up the solution.

Still didn’t get it.

But then I processed that we would first store the element:index pairs in a dictionary(hash). Then we would go and loop through the list and find complement of the target.

What this means is say the list is [2,7,11,15] and target is 9

in the first iteration. complement would be 9-2=7

now we would need to check if 7 exists in the dictionary if yes then we need to know its index. If it is not same as 2’s index that is 0 then we can return this pair. As we cannot use the same value twice.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp = {}
        # Store values in the dictionary
        for i in range(len(nums)):
            temp[nums[i]] = i
        
        # lookup for pairs
        for i in range(len(nums)):
            complement = target - nums[i]
            if(complement in temp and i != temp[complement]):
                return [i, temp[complement]]
        return []

There was another interesting approach in the solution.

one pass. Which means only one loop.