In worst-case scenario, we do ${n \choose 2}$[^1] iterations just to check whether we have a matching pair.
[^1]: Binomial derived from the combinations formula $\frac{n!}{r! \left ( n-r \right )!}$ — we can say that $n$ is the number of elements we have to check, and we have to choose $r$ of them without any order to check the summation. This algorithm has a polynomial time complexity where it grows proportionally to the square of the input size $n$. Unfortunately our algorithm takes $O(n^2)$ time to complete. **Space Complexity** — We only use two `for` loops which involves constant variables as indexes $x$ and $y$. And also, we don't use any extra space. So, our algorithm's space complexity will always be $O(1)$. We know that first approach is bad but can we improve the algorithm and make it a bit faster? What happens if we first _sort_ the array? --- ## 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 second approach. ### First Operation First, we have to sort the array in ascending order[^2]. In order for the algorithm to work this must be done and then only we can continue. [^2]: You can do it either way. We can sort in **descending** or in **ascending** order. But we have to make sure we swap the _comparing indexes_ along with the _conditions_. But for now let's stick to ascending order to make things simpler.  ### Second Operation Then we can allocate two pointers from _left_ and _right_ to walk through the elements $n - 1$ times and operate on these two numbers.  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)$ time. But remember we still have to walk through our $n - 1$ times which is equivalent to $O(n)$. ### Third 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 + 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 $n$th iteration. Our loop starts from $x = 0$ and $y = 7$. At this point our $x$'s element is $-4$ and $y$'s element is $13$ (see figure 4). If we add up those two numbers together, we get a total of $9$ which is _less_ than our target sum $10$. In this case **we move the $x$ pointer to the right side**. Basically, incrementing $x$'s index by $1$. That way we can guarantee that in next iteration we would always get a sum $> 9$.  Alright, in the last iteration we moved $x$ by $1$ and now we are at $x = 1$ and $y = 7$ (see figure 5). Once again, if we sum up $-1$ and $13$ we get a total of $12$. Now, this is _larger_ than our expected target sum. In this case **we move the $y$ pointer to left side**. Saying that we want to decrement our $y$ pointer by $1$.  Got the point? We do this iteratively until matching the target sum or until $x$ and $y$ meets together at the same index.  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 JavaScript code for this algorithm now. ```javascript function solve(array, targetSum) { const sorted = array.sort((a, b) => a - b); let x = 0; let y = sorted.length - 1; while (x < y) { if (sorted[x] + sorted[y] === targetSum) { return [sorted[x], sorted[y]]; } else if (sorted[x] + sorted[y] < targetSum) { x++; } else { y--; } } return []; } ``` While this approach is slightly better than the first, we are back to square one. Why? Well, it's the same reason as before; it does not scale well enough for larger arrays. Let me show you the problem. ### Problem Analysis First, we need to understand the cost of sorting things. [Browsers have implemented stable and well optimized algorithms for `Array.sort()`](https://stackoverflow.com/a/236534). But assume that the `sort` function chose `mergesort` as our sorting algorithm. It is guaranteed that mergesort runs in $O(n \ \log(n))$ time using $O(n)$ space. And since we only used one `while` loop to drive the state of $x$ and $y$ pointers, we get $O(n \ \log(n)) + O(n)$ which is equivalent to $O(n \ \log(n))$ in total time[^3] and $O(n)$ for space. [^3]: Remember, in _time_ and _space_ complexity analysis we always pick the **dominant** term.  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? 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 our target sum is (let it be $z$). - We already know one of our addends[^4] (let it be $x$). [^4]: What I'm referring to is the current element while walking through the array. So, basically we have two variables at hand before even doing any operations. So, we could write an equation like $x + y = z$ to represent it (where $y$ is unknown). Where we can _isolate the unknown_ variable. Say for example, $(x + y) = z$ $\iff$ $y = (z - x)$ > **Inverse Operations** > > To isolate a variable, we cancel out (or undo) operations on the same side of the equation as the variable of interest while maintaining the equality of the equation. > > This can be done by performing inverse operations on the terms that need to be removed so that the variable of interest is isolated. Subtraction cancels out addition, and vice versa, and multiplication cancels out division, and vice versa. Now we can find the unknown variable $y$ without any combinations or two pointers. The only caveat is that we need a way to memorize this calculated value as we go through the array. ### Solution Using some extra space is okay as long as its 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 = \{ i \in A \mid S - A_i \} $$ $$ \therefore \exists i \in A, \ \ P(i): \ (A_i \in R \ \lor A_i \notin R) $$There exists $i$ such that may or may not be a member of $R$.
### Elaboration We need a loop $\sum_{i=0}^{n - 1}$ that goes through each element of the array starting from index $0$. We need to calculate the inverse set within the loop[^5] so, we create an empty set $R = \emptyset$ and then for each element we calculate $y = z - A_x$[^6] and now we can place a predicate that checks $A_x$ existence in inverse set $R$ like $P(x): (A_x \in R)$ then return $\{ A_x, y \}$ if $P(x)$ is true. Otherwise, $\neg P(x)$ we union our inverse set with the calculated $y$ value where $R \gets R \ \cup \{ y \}$ and we keep on looping until $n - 1$. [^5]: We could also do a pre-computation of the inverse set before the loop. Since it does not affect the running time of the algorithm, it's up to you to decide! [^6]: $x \in A$ > **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`.  As illustrated, in the first iteration we start off with an empty set named $R$. Initially our loop starts from index $0$ where $i$ is the index variable. In the first iteration we don't have any elements. So, therefore we immediately add the calculated value $2 = -5 - (-7)$ to the set $R$ and move on to the next element.  In the second iteration, first we check whether element at index $1$ is an element of $R$. We can see that $-5 \notin R$ so, we add our inverse calculation $0 = -5 - (-5)$ to set $R$ and continue.  In the third iteration, again we check whether element at index $2$ is an element of $R$. We can see that $-3 \notin R$ so, we do our inverse calculation $-2 = -5 - (-3)$ and add it to set $R$ and continue.  Fourth iteration already! Again we check whether element at index $3$ is an element of $R$. We can see that $-1 \notin R$ so, we do our inverse calculation $-4 = -5 - (-1)$ and add it to set $R$ and continue.  We are in the fifth iteration! And would you look at that! We just found $0$ in our set $R$. This means our inverse got a match! Now we can return these two elements like $\{ A_x, -5 - A_x \}$ where $A_x$ is $0$. Woohoo now we have an idea on how it works, let's write the pseudocode. ```javascript function solve(array, targetSum) { const records = new Set(); for (let x = 0; x < array.length; x++) { let y = targetSum - array[x]; if (records.has(array[x])) { return [array[x], y]; } records.add(y); } return []; } ``` ### Time & Space Complexity In this approach we solely rely on dynamic programming techniques. And we were able to solve it in $O(n)$ time and $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!