Solving Array Problems: Two Sum
Algorithms and Data Structures From Zero to Hero
Given an array of integers
nums and an integer
target, return indices of the two numbers such that they add up to
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Understanding with examples
Input: nums = [1,2,3,4,5], target = 8
Explanation: Because nums + nums == 8, we return [2, 4].
Analysis — BigO
My first solution will be to iterate through the array starting at index 0 and then create a nested loop to iterate through the rest of the array elements.
The value a represents the value of the upper loop and the value b the index of the elements to the right of the array that will be iterated in the inner loop, until the indexes of the two numbers add up to the target.
If a at index 0 plus one of the elements on the right hand side of the array is not the sum of the target, the pointer changes to the next one until
b add up to the target.
As this is a nested loop, this operation will take O(nxn) which is actually O(n^2).
I can do it a better.
The second solution will be to create an object. The object will have the value, and the index.
I’ll have to create an
obj variable and iterate through the array. On each iteration it will add the item and the related index.
Next, I’ll create another (non-nested) loop, iterate through the array and create a variable
augend the number to which an
addend is added (mathematical and computer science term for the number on the left in an addition, the number on the right is the addend).
Finally, If the
augend, we return the output.
These separates iterations will take O(n).
Similar to the second solution but more simple using the map function.
Create a new Map()
map and an
augend variable, then iterate through the array, get the
augend and check if is in the map if isn’t add the value and index to the map until found it.
This is an easy problem, if there is something you don’t understand don’t be afraid to leave a comment.
This article is part of the series Algorithms and Data Structures From Zero to Hero.
👋 Let’s be friends! Follow me on Twitter and connect with me on LinkedIn. Don’t forget to follow me here on Medium as well.