Two Sum Problem in Python

The two sum problem is a version of the subset sum problem and is a common programming question. Although there is a popular dynamic programming solution for the subset sum problem, we can construct an O(n) time approach for the two sum problem. The goal is to identify all the pairs of two numbers that add up to a certain “S” in an unsorted array. This article is about a famous coding task frequently asked in Python interviews.

Solving Two Sum Problem in Python

Your approach to this topic will be determined by your level of expertise. One method is to loop through the list, comparing each item to the rest. We’ll go through two different techniques you can use to remedy this issue.

Problem Statement: Return all pairs of two numbers whose sum equals a given target from an array of integers. You can assume that each input has just one rational answer and that the same element cannot be reused.

Let’s start with explaining the problem statement and then move on to the possible solutions. This truly means that we need to construct a function to check if there are any values in this array that add up to the provided target number. We’ll provide a basic example to describe the problem and solution.

Assume we were given the numbers [4, 6, 1, -5, 8], and the target sum was 9. We want to see if this array has a pair of numbers that add to the supplied target sum. As you can see, the procedure should return 8 and 1, which sum up to 9 as the desired total. So, what is the best strategy for dealing with this issue? Refer to the following sections:

Solution 1:

The first answer that comes to mind is to repeat the loop twice. The native technique uses two for loops and travel over the full array twice to reach the intended sum.

So, we’d walk through the array one at a time. In this manner, you need to check the rest of the array to know if the sum equals the number value specified while going through all the numbers.

For example, we may continue with 4 and work our way through the rest of the numbers [6, 1, -5, 8] to determine if adding 4 to any of them provides 9 or not. We’ll move to the next number, 6, and check the numbers likewise [1, -5, 8] to see if adding the number 6 to any of the numbers presented in the array gives 9, before continuing the process through the array. The Python code for a two sum problem with two for loops is shown below.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/03/echo/huj-1.png" data-lazy- height="112" src="data:image/svg xml,” width=”529″>

The idea is to bring out that while doing so may not be the most efficient use of time. It is still a viable option. Two for loop will result in O(n2) time complexity since traveling two times utilizing two for loop would mean traversing n2 time in terms of time complexity. Because we are not storing any integers, the space complexity is O(1).

The second solution is a sorting method. Although the method might take up more space, it is more efficient without any doubt.

Solution 2:

We will utilize the sorting algorithm in this manner since sorting requires nlog(n) time-steps, which is considerably more efficient than O(n2), employed in the previous strategy with two for loops.

The array’s numbers are sorted first in this approach. We’ll have two pointers, one on the left at the first number in the array and the other on the right at the last number in the array.

We’ll simplify this problem again by using the prior array example of [4, 6, 1, -5, 8]. The data is then sorted to reflect a sorted array of [-5, 1, 4, 6, 8]. Our left pointer (indicated as l_pointer) will be set to -5 and our right pointer (indicated as r_pointer) to 8. We’ll see if -5 8 equals 9, which is the specified total. No, because 3 is less than the stated sum of 9. We shall shift our cursor in ascending order, from left to right.

Now, we’ll go back to 1 and see if the addition of 1 and 8 equals 9, which it does. This gives us the pair we’re looking for. The pairings 1 and 8 will now be printed as the pairs that will provide the required two numerical sums.

Let’s talk about this issue a little more. Consider the following scenario: if the target sum is ten and the sum of one and eight is less than ten, the left pointer will be moved up to four in ascending order. The total of 4 and 8 equals 12, which is greater than the goal total.

As a result, we’ll shift the right pointer in descending order from right position to left. The left pointer is now at 4, while the right pointer has moved to 6. In this situation, we’ve reached the requisite pair of 4 and 6, which will give us the required amount of 10. The following Python code shows how the previous information is implemented below:

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/03/echo/huj-2.png" data-lazy- height="214" src="data:image/svg xml,” width=”555″>

We utilize O(nlogn) in terms of time complexity due to sorting, which is better than the previous solution’s method, and it is a little more expensive because it uses O(nlogn).

Conclusion:

In this article, we examined the well-known Python two sum problem and offered two viable solutions for you to consider. We have added two solutions to fix this two sum problem in Python. These examples can be applied in different ways as per the user’s needs. We hope you found article helpful. Check out other Linux Hint articles for more tips and information.