Leetcode problem : https://leetcode.com/problems/two-sum/
Brute force solution :
- Fix the first pointer to the first element of the array.
- We assume that this element is the first number in our output pair.
- Now to find the next number of the pair, we can take the difference between the target and the element pointed by the first pointer (first element).
- Now to find the location of the second element, take a second pointer and iterate from the second index of the array till its end.
- If found, we can return the index of both the elements (values of both the pointers).
- Else, we increment the first pointer and take its difference with the target.
- Then we iterate the second pointer from the third index till the end of the array.
- This can be implemented using two for loops and hence takes O(n^2).
Optimized solution:
- We can use an object (or hash map). Why? Because we can fetch an item from objects at O(n) complexity which is more efficient.
- Our aim is to implement this solution in a single for loop.
Intuition :
As we iterate through each element in the array,
- We need to keep track of the elements that we previously iterated. Hence, we can store the previous elements along with their indices in an object.
- We are simultaneously calculating the difference of that current element with the target. We then check whether the object(acts like a store) already has that difference (which is the second number in the output pair).
- If yes, return the value corresponding to the difference in the object (first index) and the current pointer (second index) from the loop as an array.
- If not found, store the current element and the pointer value(which is its index) as a key value pair in the object. As it had become a part of the previously tracked elements.
Top comments (0)