DSA TWO SUM Problem explained to a beginner

We all know the famous Two sum problem ,

As an individual who has been grinding leetcode and better at solving DSA problems, this problem might look easy for you. But for a beginner who is getting started with DSA, this problem seems like the hardest one ever seen.

Feel free to skip reading if you are already familiar with it : )

What made me write this Article?

Well, we know that whenever we speak of starting DSA, we know that this problem definitely comes under the list to do.

Trust me, I have solved it more than 3 times using different approaches, but every time when i revisited after a few months or weeks gap let’s say, it’s completely blank as to where i should begin with to solve the problem. This could be due to lack of practice or various other reasons😅.

So, i immediately thought of writing about it to explain step by step on what’s happening and how to approach to the solution.

Let’s not delay anymore🥱

Problem statement:

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.

Explanation:

Let me break it down for you.

So, the problem says that

• there is an array (list) called nums which contains all integers.

• upon adding any of the two elements in the array, they add up to the given target number

• We can consider that for each input array given there can be exactly one pair of elements which sum to the target. It means that there is only one solution or one subset of array satisfying the given condition.

• And we need to return the indices of those numbers

Let’s take an example.

nums = [ 1, 2, 3, 4 ], target = 6

In this example, we need to find the two elements in the array whose sum is equal to the given target which is 6 in this case. By looking at the example we can simply say that [2,4] satisfies the given condition so the output will be [1,3] (indices of [2.4]).

How do we approach this in programming?

The Brute force Approach:

Before you think of how you can efficiently solve the problem with less time complexity, it is important to first solve it with brute force approach and then optimize it.

First step we always think of whenever we have an array as our input is to loop through it. In our case, we need to traverse the array and check each element with every other element to see if they add up to the target.

Python

def two_sum_brute_force(nums, target):
    n = len(nums)
    # Outer loop iterates from the first element to the second-to-last element
    for i in range(n):
        # Inner loop iterates from the element after 'i' to the last element
        for j in range(i + 1, n):
            # Check if the sum of the current pair equals the target
            if nums[i] + nums[j] == target:
                return [i, j]  # Return the indices if a pair is found
    return []  # Return an empty list if no pair is found

Reading the above point itself explains it's time complexity is high. So we definitely need to optimize the solution.

As you know,

it's not about just solving the problem, it’s about solving it efficiently.

Approach 2 (Using Hashmaps):

Don't worry about the fancy term hashmaps, it is simply a dictionary which is constructed based on some mathematical function. You can read more about it here.

In this approach, We do the reverse thinking. Let me elaborate.

let’s say, generally, if a+b = c then b-c = a right?

We will be doing the same here.

Algorithm:

Step1: Take a hashmap, and loop through the index and element of the given array

Step2: Check if the (element - target) present in the hashmap.

Step3: If it is, then we return the result else we add it to the hashmap with the key being the element and index being its value.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {} # step1
        for index,element in enumerate(nums):
            if (target-element) in hashMap: # step2
                return [i,hashMap[target-element]]
            else:
                hashMap[element]=i #step3

For our example, nums = [ 1, 2, 3, 4 ], target = 6, the hashMap will look like this.

hashMap = {1:0, 2:1, 3:2}

for the last iteration, (6-4) = 2 already present in the hashMap so we return [3,1] ( remember we can return the indices in any order).

We reduced the time complexity to O(n)

I hope this helps you in understanding the problem and how to approach it. I am sure there are lot many ways to do it. Let me know in the comments I am happy to learn :)

If you need more clearer explanation or any assistance, you can book a session with me on topmate.

Feel free to connect with me on LinkedIn.

If you find this helpful at all, you can support me by buying me a coffee.☺️

Thank you for reading. Happy Learning!❤️