Two Sum

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 th…


This content originally appeared on DEV Community and was authored by Vinay Krishnan

Leetcode problem : https://leetcode.com/problems/two-sum/

Brute force solution :

  1. Fix the first pointer to the first element of the array.
  2. We assume that this element is the first number in our output pair.
  3. 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).
  4. 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.
  5. If found, we can return the index of both the elements (values of both the pointers).
  6. Else, we increment the first pointer and take its difference with the target.
  7. Then we iterate the second pointer from the third index till the end of the array.
  8. This can be implemented using two for loops and hence takes O(n^2).

Optimized solution:

  1. 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.
  2. Our aim is to implement this solution in a single for loop.

Intuition :

As we iterate through each element in the array,

  1. 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.
  2. 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).
  3. 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.
  4. 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.


This content originally appeared on DEV Community and was authored by Vinay Krishnan


Print Share Comment Cite Upload Translate Updates
APA

Vinay Krishnan | Sciencx (2022-03-26T11:01:27+00:00) Two Sum. Retrieved from https://www.scien.cx/2022/03/26/two-sum-2/

MLA
" » Two Sum." Vinay Krishnan | Sciencx - Saturday March 26, 2022, https://www.scien.cx/2022/03/26/two-sum-2/
HARVARD
Vinay Krishnan | Sciencx Saturday March 26, 2022 » Two Sum., viewed ,<https://www.scien.cx/2022/03/26/two-sum-2/>
VANCOUVER
Vinay Krishnan | Sciencx - » Two Sum. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/03/26/two-sum-2/
CHICAGO
" » Two Sum." Vinay Krishnan | Sciencx - Accessed . https://www.scien.cx/2022/03/26/two-sum-2/
IEEE
" » Two Sum." Vinay Krishnan | Sciencx [Online]. Available: https://www.scien.cx/2022/03/26/two-sum-2/. [Accessed: ]
rf:citation
» Two Sum | Vinay Krishnan | Sciencx | https://www.scien.cx/2022/03/26/two-sum-2/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts