What Are The Two Sums? from Ishita Juneja's blog

Targets are the motivation behind every task! 

Usually, the codes you generate are to meet certain targets or outputs for the user. Similarly, when you give a target to an array and its element, a two-sum problem is formed. 

Many times you are asked to print all subsequences of a stringor array such that they follow a specific condition. Such as the sum of two elements in these subsequences results in a certain value. This type of problem is called a twosumproblem. 

This article will guide you throughout the explanation of this problem as well as the process of solving it through different approaches. 

To ensure that you understand the concept and solution of this problem, it is important to establish a foundation with the logic behind it. 

Let's first discuss the logic behind the two-sum problem. 

What are two sum problems?

Two sum problem is a medium difficulty level coding problem. In this problem, the programmer is given a task to scan through an array for a set of elements. 

This set must contain only two elements and the sum of these elements must be equal to a predefined target. 

This target is given to the programmer in the problem statement itself and hence can change for different problems. 

The logic behind this problem is to find two elements that sum up to get a value of a single digit. 

This function will return true and the elements if the appropriate elements are found. Else, it will return zero. 

For example, let's say the target is 5 and we ask you to scan through an array A such that the sum is 5.

(Let A={1, 2,3,5,6,7,8}) 

In this example, the function can easily return the set {2, 3} as a sum to form 5.

You must know the searching and conditional operations on arrays to solve this problem accurately. 

Let's see how the problem statement of two sums is framed. 

Problem statement for Two sums

In this problem, you are given an array of integers and a sum number as a target. You have to generate a code in which the array returns an array of elements that sum to result in the target sum. Else, if not found, return an empty array from the function. 

Now, given this kind of problem statement, you can have various paths to move forward. Let's have a look at ways in which you can resolve two sum problems efficiently. 

How can you resolve two sums?

In general, there are three ways to resolve this problem and generate efficient code. Let's discuss each method and how it works in detail. 

Through brute force method

The most basic method of finding an array of elements that sums up to any certain value is through the brute force method. 

In this method, an empty array is declared initially and then the values are checked one by one. Each set of elements is checked by the function individually. 

If the elements are found, they are transferred into the empty array and returned to the user. However, in case they are not found, the empty array as it is will return. 

Following are the steps showing the application of this approach:

• The first step is to run a loop. This loop will ensure that the first value of this array is fixed

• Now, run another loop. This loop allows the code to make a solution for every element of the first loop element.

Let's say the target is 5 and the elements are {1, 2,3,5,6,7}. The first loop will run for elements 1,2,3 only. However, the second loop will fix the value of the second digit to attain the sum {2, 3} and {3, 2,}

• In case the loops intersect and return the value of elements that combine to form the target value, print the return. 

Through two pointer

The second method is to sort an array and then apply the two-pointer technique. In this method, two pointers are applied at either end of an array. The first value is fixed by the first pointer and the second value is determined likewise. 

As the pointer moves in an array, it finds the element which will combine with the first element to result in the target sum. 

Following are the steps through which this method is executed:

• Declare two pointers for a sorted array as left and right. 

• Place the left pointer at the first end to fix the value of the first element of the array

• Next, move the second pointer through binary search and check if it can reach the target sum with the first element. 

• Repeat the process for all the possible rounds and attain the possible array of elements. 

Return the values at these pointers and you will get the elements of an array that sum up to form the target sum. This method is highly efficient and the process is faster than the brute force method. 

Through Hashmap

Using a hashmap is one of the most convenient methods to resolve the two-sum problem. In this method, traversing an array is done. Each element is checked if the targetsum-x added to the target sum will give the accurate value or not. 

The algorithm through which this method is completed includes the following steps:

• Firstly, you will have to declare an empty hash table or tables

• Check whether A[i]-x and A[i] fulfill the requirement and sum together to form the target sum or not. Make sure you check this condition for each value

• Once found, print the pair A[i], x-A[i].

• Else, insert the value of A[i] into S(a different block) 

This way, you can easily print the values of elements that sum up to the targetsum without taking a long execution time. 

Winding up