LeetCode: Problem #1 — Two Number Sum
Given a non-empty array containing unique integers and a target sum, you have to write a function that should return an array containing any two unique numbers from the input array; however, if there are no pair of numbers that sum up to the target sum, the function should return an empty array.
Array: [-2, 5, 6, 3, 4, 5, 9, 7]
Target sum: 14
Output: [5, 9] # [9, 5] works as well, but you can’t add an integer to itself so [7, 7] does not work
There are a few ways to solve this problem with varying space-time complexities, so let’s go ahead and get started with the least efficient approach — using a nested loop.
Nested Loop | Time: O(n²) | Space: O(1)
Looking at the bigger picture, this function twoNumberSum utilizes 2 for-loops, which explains it having a time complexity of O(n²) where nis the length of the array. By having 2 nested for-loops, this would require a total of 2 iterations of the input array, 1 for each for-loop.
Now, let’s review each line 1-by-1.
- In the first line def twoNumberSum(array, targetSum):, the def keyword allows us to define a function in Python, in this case, named twoNumberSum and this function accepts 2 parameters — array & targetSum.
- In the second line for i in range(len(array)-1):, this creates our for loop where i represents the index or number starting from the beginning to the end of the range for each iteration. Given the example array above ([-2, 5, 6, 3, 4, 5, 9, 7]), len(array) calculates to 8 and range(len(array)-1) calculates to range(8–1) or range(7). The range function in Python defines a range that begins from 0 up to and does not include the number specified, or in this case, 7. Thus, range(len(array)-1), or range (7), is equivalent to 0, 1, 2, 3, 4, 5, 6, and i represents each of these numbers incrementally with each iteration. Conveniently, if you are just looking to iterate as many times as there are elements in the array, you can simply use range(len(array)), so by using range(len(array)-1), we are simply iterating as many times up to but not including the last element in the array.
- In the third line for j in range(i + 1, len(array)):, this is another for loop, no different from the previous line except that we are now defining a new variable called j to represent a number starting from i + 1 up to but not including the length of the array. Therefore, when i is 0, j will be 1. If there are 2 parameters specified in a range function, the first parameter specifies a starting point inclusive and the second parameter specifies an ending point not inclusive. In other words, for the first iteration, range(i + 1, len(array)) will be range(1, 8) and will iterate from the second element to the last element of the array.
- In the fourth line if array[i] + array[j] == targetSum:, we are indexing into the array with our i and j variables that we defined in our for-loops, and we are using an if statement to check if there are any combinations or pairs of i & j, when added together, equate to the targetSum.
- In the fifth line return [array[i], array[j]], if our if statement’s condition is satisfied, we are simply returning from our twoNumberSum function an array containing our unique pairs that add up to the targetSum.
- In the sixth line return , we are turning an empty array once we iterate through our nested for-loops without ever satisfying the if statement from the fourth line
- Finally, in the final line print(twoNumberSum(array, targetSum)), we are printing our invocation of the function twoNumberSum with our arguments array ([-2, 5, 6, 3, 4, 5, 9, 7]) & targetSum (14) that we defined separately above.
On a final note, we have to remember that we cannot use any single integers twice from the array but unique pairs of numbers that add up to the target sum. This is exactly why we utilized a nested for-loop here with i starting its iteration from the beginning of the array and j starting its iteration from the 2nd element from the array instead of the 1st element from the array like i. By doing this, we will essentially check every possible unique pair with the last pair being i as the 2nd to last element in the array and j as the last element in the array.
Sort | Time: O(nlog(n)) | Space: O(1)
The sort solution is more efficient than its nested for-loop counterpart because it utilizes the sort() method in Python, which uses an effective sorting algorithm behind the scene such as quick sort, merge sort, or even heap sort. Each of these sorting algorithms have a time complexity of O(nlog(n)), which is more efficient than O(n²).
Let’s examine the code above even further…
- array.sort() utilizes the built-in .sort() method from Python. Do not confuse this with the other built-in method from Python called .sorted(). The main difference is that .sort() does not return a new array but sorts the array in-place, whereas .sorted() returns a new sorted array without modifying the original array.
- We implement the concept of left and right pointers. Pointers can be simply understood as a way to keep track where we are at, almost like an index. In this case, the left pointer is defined at index 0, whereas the right pointer is defined at the index of the last element of the array.
- We use a while loop for as long as the left pointer is less than the right pointer, we immediately check if the element of the array at the left pointer index added with the element of the array at the right pointer index equals to the target sum. If so, we return an array containing the two elements.
- However, if the sum of the two elements is less than the target sum, we increment the left pointer by 1 because we know that in the next iteration, we can achieve a bigger sum (hopefully equal to the target sum) by adding the element at index 1 instead of 0 with the last element in the array. On the other hand, if the sum of the two elements is more than the target sum, we increment the right pointer by 1 so we can achieve a smaller sum.
- Lastly, if our if statement within the while loop for any of the iterations is not met, then we return an empty array and print the invocation of the function with array & targetSum as its 2 arguments defined elsewhere.
On a last note, the total time complexity is O(nlog(n)) from the sorting in the beginning, and the total space complexity is O(1) because we don’t use any additional space, likewise with the nested loop approach.
Hash Table | Time: O(n) | Space: O(n)
Using a hash table will serve as the most optimized approach out of the 3 solutions. The time complexity is O(n) where n represents the length of our input array, and we are traversing through our array only once. The space complexity is O(n) because we are adding and storing values to a hash table.
Let’s examine the code even further…
- We define nums as a variable that is an empty dictionary or hash table at first. Hash tables, hash maps, or maps can be interpreted differently for each programming language, but in Python, it can be interpreted as a dictionary.
- We are iterating through our array using a for-loop, and because we are given the targetSum and element that we are currently iterating from the array, we can calculate what the potentialMatch is. potentialMatch represents the number that when added with the element that we are currently iterating from the array adds up to the target sum.
- We use an if statement to check if the potentialMatch is in the hash table or nums dictionary. If potentialMatch is in the dictionary, we will return an array containing the potentialMatch and the element that we are currently iterating from the array. However, if potentialMatch is not in the dictionary, we will simply add a new key and value pair in the dictionary consisted of the current element we are iterating from the array as the key and anything as its value (in this case, we just use a Boolean value of True). We do this because, in future iterations, the element that we were currently iterating from our array may serve as the potentialMatch to other numbers that we will traverse through from our array.
Here are 3 approaches above that explore the Two Number Sum problem in varying efficiency. I hope this is insightful for anyone out there, and this marks the beginning of a new journey to prepare me for the technical interview at MANGA (Meta, Amazon, Netflix, Google, Apple) companies.