Write a function that returns an array of two numbers that adds up to a given input (Target Sum)

There are several ways to approach this problem, each with different time and space complexities.

The brute Force Approach will go through the whole array with two for Loops with O(n²) time complexity, so let’s not get into that now, Smart way is to picture this question mathematically,

if we have to find two numbers that adds up to the target sum, the equation would be like

As we traverse through the array we will find the unknown value for j, and if j is in the given List of Possible numbers that means we have got the two numbers (i, j) that will sum up to the target sum.

we can use a Hash map to store the i values, thus the lookup is O(1)

Rust Code

Code available here

Implementation is Simple as we just have to traverse through the given array using a for loop and update the hash table, and if we find a match that is (i + j = TargetSum) then we return [i,j] else we return empty vector in the end of the iteration.

Output

Time Complexity is O(n) as we traverse through the array once.

Space Complexity is O(n) as in worst case the hash table might hold the whole input array.

Heuristic Learning.