By Yasin

We want to write a function that takes a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the process should return an empty array.

First Approach

My first approach would be to go through the array of integers in a brute force manner. Suppose we have an array of numbers [ 1, 2, 3 ] like: -

Sample array of numbers i.e., [1,2,3]
Figure 1 — An array of numbers.

We need to figure out all the two-element combinations it can have. If we think about it, we would probably end up doing something like this: -

Sample array of elements combinations i.e., { (1,2), (1,3), (2,3) }
Figure 2 — Combinations of array of numbers [ 1,2,3 ][\ 1, 2, 3 \ ] which yields { (1,2),(1,3),(2,3) }\{\ (1,2), (1,3), (2,3) \ \}

Conceptually in this approach, we try to achieve a reducing set of combinations for two numbers and do some calculation with it. If we can align this approach as a solution to our challenge statement, we could assemble the brute force algorithm we talked about. Roughly it should be like the following: -

  • An outer loop which goes through each of element until n1n-1
  • An inner loop which goes through n+1n+1
  • A condition to check the summation
Program Input

Say we have an array [ -1, 5, -4, 8, 7, 1, 3, 11 ] and a target sum 14. Now let's transform above steps into a pseudocode.

If we were to execute this algorithm, what are the different combinations we go through? Let's write down the iterations and their respective combinations manually.

IterationChecked Combinations
1(-1,5), (-1,-4), (-1,8), (-1,6), (-1,1), (-1,3), (-1,11)
2(5,-4), (5,8), (5,6), (5,1), (5,3), (5,11)
3(-4,8), (-4,6), (-4,1), (-4,3), (-4,11)
4(8,6), (8,1), (8,3), (8,11)
5(6,1), (6,3), (6,11)
6(1,3), (1,11)
7(3,11)

Did you see that? in worst-case scenario we had to evaluate 2828 pairs and in the 77th iteration we found our matching number pair (3,11)(3, 11). However, it's not the same always. It will change based on the indices and therefore combinations will be lesser if we break out of the loop after a successful match.

Now let's do a quick analysis of our 1st solution.

Can we do better?

We know that first approach is bad 😕 but can we improve algorithm and make it a bit faster? What happens if we sort the array huh 🤔?

Second Approach

There's a second way of solving this problem. And it's slightly better than the first one. Initially, in the challenge statement, I didn't mention whether the array is sorted or not. So, what if we sort the array first in ascending order and then figure out a way to solve this?

Program Input

Say we are given a new array [ -4, 13, 1, 3, 5, 6, -1, 11 ] and a target sum of 10. Let's use these inputs for our 2nd approach.

1st operation

First, we have to sort the array in ascending order*. In order to algorithm to work this must be done and then only we can continue.

Two summation approach 2 step 1: Sorting the array in ascending order
Figure 3 — Sorting our array of numbers in ascending order.

2nd operation

Then we can allocate two pointers from left and right to walk through the elements n1n - 1 times and operate on these two numbers.

Two summation approach 2 step 2: Allocating pointers
Figure 4 — Allocating the pointers. Set xx to index 00 and yy to the last index n1n - 1.

This way we can solve the problem more optimally instead of using two for loops. With a reasonable sorting algorithm like mergesort or quicksort we could sort the array in n log(n)n \ log(n) time. But remember we still have to walk through our n1n - 1 times which is equivalent to O(n)O(n).

3rd operation (doing the summation)

So far, now we know the array must be sorted first, and we need two pointers to compare. The core logic of this approach is to drive algorithm's state using three predicates.

We need to check whether the sum of A+BA + B: -

  1. Is it equal to target sum?
  2. Is it less than target sum?
  3. Is it greater than target sum?

Let's try to write down the algorithm. Remember that, up to this point, we assume that we have already sorted the array and allocated the two pointers. Now it is time to evaluate the above conditions against each pair in every nn'th iteration.

Our loop starts from x=0x = 0 and y=7y = 7. At this point our xx's element is 4-4 and yy's element is 1313 (see figure 5). If we add up those two numbers together, we get a total of 99 which is less than our target sum 1010. In this case we move the xx pointer to the right side. Basically, incrementing xx's index by 11. That way we can guarantee that in next iteration we would always get a sum >9\gt 9.

Two summation approach 2 step 3 (loop): First iteration
Figure 5 — 1st iteration

Alright, in the last iteration we moved xx by 11 and now we are at x=1x = 1 and y=7y = 7 (see figure 6). Once again, if we sum up 1-1 and 1313 we get a total of 1212. Now this is larger than our expected target sum. In this case we move the yy pointer to left side. Saying that we want to decrement our yy pointer by 11.

Two summation approach 2 step 3 (loop): Second iteration
Figure 6 — 2nd iteration

Got the point? we do this iteratively until matching the target sum or until xx and yy meets together at the same index.

Two summation approach 2 step 3 (loop): Third iteration
Figure 7 — 3rd iteration

Well, would you look at that? We reduced the number of iterations we have to go through! We have accomplished significant progress in making this algorithm a bit faster. Now that we found our number pair, we can finally return the result and halt the algorithm.

Let's write the pseudocode for this algorithm now.

We can do better!

The algorithm we wrote runs in linearithmic time which tells us its complexity grows proportionally to the array input size with a logarithmic factor 😕. What can we do about it, huh? Can we solve it in linear time?

Dynamic Approach

Up until now, all the approaches we have taken is not very optimal from a time standpoint. Fortunately, there's one other way of solving this problem in a much cooler way. You might have thought about this already from the previous approach. But first, let's list down the things we already know: -

  • We know what's our target sum is (let it be zz).
  • We already know one of our addends* (let it be xx)

So, basically we have two variables at hand before even doing any operations. So, we could write an equation like x+y=z\large{x + y = z} to represent it (where yy is unknown). Where we can isolate the unknown variable. Say for example, (x+y)=z\normalsize{(x + y) = z}     \normalsize{\iff} y=(zx)\normalsize{y = (z - x)}

Now we can find the unknown variable yy without any combinations or two pointers. The only caveat is that we need a way memorize this calculated value as we go through the array.

Solution

Using some extra space is okay as long as it's complexity grows in a reasonable size. Now what do you think? for our solution should we use a hashmap? what about a set?

You'd see a lot of examples of two summation problem's dynamic approach in the internet uses a hashmap auxiliary space implementation. But we really do not need key-value pairs for our solution. Instead, simply we can use a set of numbers to track the inversion results.

Formal Proof

R={iASAi} iA,  P(i): (AiR AiR) \large{R = \{ i \in A \mid S - A_i \}} \\~\\ \therefore \large{\exists i \in A, \ \ P(i): \ (A_i \in R \ \lor A_i \notin R)}
There exists ii such that may or may not be a member of RR.

Elaboration

We need a loop i=0n1\sum_{i=0}^{n - 1} that goes through each element of the array starting from index 00. We need to calculate the inverse set within the loop* so, we create an empty set R=R = \emptyset and then for each element we calculate y=zAxy = z - A_x* and now we can place a predicate that checks AxA_x existence in inverse set RR like P(x):(AxR)P(x): (A_x \in R) then return {Ax,y}\{ A_x, y \} if P(x)P(x) is true. Otherwise, ¬P(x)\neg P(x) we union our inverse set with the calculated yy value where RR {y}R \gets R \ \cup \{ y \} and we keep on looping until n1n - 1.

Switching to new inputs

For this approach let's use the array [ -7, -5, -3, -1, 0, 1, 3, 5, 7 ] and the target sum -5.

First iteration of two summation dynamic approach
Figure 9 — 1st iteration.

As illustrated, in the first iteration we start off with a empty set named RR. Initially our loop starts from index 00 where ii is index variable. In the first iteration we don't have any elements. So, therefore we immediately add the calculated value 2=5(7)2 = -5 - (-7) to the set RR and move on the next element.

Second iteration of two summation dynamic approach
Figure 10 — 2nd iteration.

In the second iteration, first we check whether element at index 11 an element of RR. We can see that 5R-5 \notin R so, we add our inverse calculation 0=5(5)0 = -5 - (-5) to set RR and continue...

Third iteration of two summation dynamic approach
Figure 11 — 3rd iteration.

In the third iteration, again we check whether element at index 22 an element of RR. We can see that 3R-3 \notin R so, we do our inverse calculation 2=5(3)-2 = -5 - (-3) and add it to set RR and continue.

Fourth iteration of two summation dynamic approach
Figure 12 — 4th iteration.

Woah! fourth iteration already? again we check whether element at index 33 an element of RR. We can see that 1R-1 \notin R so, we do our inverse calculation 4=5(1)-4 = -5 - (-1) and add it to set RR and continue.

Fifth iteration of two summation dynamic approach
Figure 13 — 5th iteration.

We are in the fifth iteration! and would you look at that! we just found 00 in our set RR . This means our inverse got a match! Now we can return these two elements like {Ax,5Ax}\{ A_x, -5 - A_x \} where AxA_x is 00.

Whoohoo now we have idea on how it works, let's write the pseudocode.

Time & Space Complexity

In this approach we sorely rely on dynamic programming techniques. And we were able to solve it O(n)O(n) time and O(n)O(n) space complexity. This is the optimal way of solving this problem.

Summary

Overall, I think even though two summation is a very easy challenge, we can learn a lot from it. How simple algebraic equations can help to solve complex problems more elegantly.

Until next time. Thanks for reading !

Published