LeetCode Two Sum Solution: Objects
Last week, I wrote about a solution to LeetCode’s Two Sum problem. My solution passed all of the test cases, to return the indexes of two elements in an array that add up to a target sum, but wasn’t exactly an efficient solution. I used a nested loop to complete the problem last week, but that solution’s time notation would be O(n²). I’d be able to improve on that Big O result by making another solution using an object in my function. Looping through the array once to create an object, then looping again to check each key-value pair in the object to find a return value for the function would be O(n), much more ideal than O(n²).
The first thing I want to do in this new solution is create a new variable set to an empty object. I want to iterate over the nums array and save every element in the array as the key of the object. Each value will be the index of the array element.
Once this object has been filled out with the array data, I want to create another loop to return the pair of indexes that the problem asks to give as a solution. This loop will check if there is a pair of elements that add up to the target that’s passed into the array. I set a new variable to check if there’s a key in the object that’s the difference of the target number and each element in the nums array. For example, if the target number is 7 and the array that’s passed in is [1, 3, 4, 8], the first loop will check if there is a key in the object of 7–1, which is 6, which won’t exist in the object because there isn’t a 6 in the array.
In my previous example, since 6 won’t exist, found will be undefined, which means the if statement will fail and the next loop will begin. Once found is truthy the pair of the current value of i and the found element will return. If the loop finishes without finding any pairs, then the loop will end and the function will return a pair of zeroes. Since two loops running next to each other instead of nested inside each other is an O(n) operation, the function will be O(n), which is much more efficient than my solution from last week!