LeetCode Challenge: Two Sum
This week, I’m working on the Two Sum LeetCode challenge. This challenge requires you to write a function that takes in an array of numbers, nums, and an integer, target, that two of the elements in the array will add up to. The function needs to return the indices of those two elements as an array.
My first impulse on how to solve this problem is to create a loop that checks each element of the array. While this loop is running, I want a second, nested loop inside of the first loop that checks each successive element while the element from the first loop is being checked.
Inside the second loop, when the two current elements being checked are equal to the target number, I want to push those two iterator variables into an empty solution array that was created before the loop began. This solution array is then returned to get a passing solution to the problem.
Even though this function passes all test cases, it’s pretty inefficient. Since the function includes a loop inside of a loop, that means that the Big O notation is O(n²), quadratic time. As the passed-in array gets longer or has a matching pair closer to the end of the array the amount of time the function takes to run will increase by an absurd amount. There are ways to make this function more efficient, which I’ll go over in a future blog post. For now, a passing function is good enough for me.