Two numbers add up to target

Given an array find the indices of two numbers such that they add up to the given target.

This is a fundamental data structure problem often asked in tech interviews. I have provided a solution here in this article which solves the problem in O(n) time and O(n) extra space. However, I think, a more efficient solution is possible which would solve it in O(1) space.

Please let me know in the comment section below if such an optimised algorithm is possible.

If there is an array arr, containing a set of numbers and also a number target. The ides is to find index pair i, j where
arr[i] + arr[j] = target. The brute force way would be to run two loops and check each element against the remaining elements in arr unless we find the indices.
However, that would require a time complexity of O(n^2).
An alternative method can be applied which uses an auxiliary hashmap (a dictionary in Python) to store the difference (target – arr[i]) as the key in the hashmap against index i of current element.
Now as we move ahead traversing the array, we check whether the element is present in the hashmap or not. If a match is found then we pick the index value against the matched key and pair it with the current element that is, arr[i]‘s index i. The pair thus obtained is the answer.

Explanation:
Let’s say we have the following array,

arr = [2,3,1,5,7] and target = 9. So, clearly the hashmap would be

hash =
{
7: 0,
6: 1,
8: 2,
4: 3,
2: 4
}

Now when we reach at the end of the array (i.e, at index 4, we bump into the element 7 which is present in the hashmap and that’s a match. So, the answer is [0, 4]).

The simple code as submitted in leetcode is given below:

  def twoSum(self, nums: List[int], target: int) -> List[int]:
        aux = {}
        len_ = len(nums)
        response = []
        
        for i in range(len_):
            if nums[i] in aux:
                return [aux[nums[i]], i]
            else:
                aux[target-nums[i]] = i
        return response      

This approach is not the most optimised one but it solves the problem in <O(n^2). Kindly post in the comments below if there is a solution to this problem with constant space complexity.

Thanks for visiting.