I'm a CodeNewbie and a recent coding bootcamp graduate who's embarked on an algorithm journey in order to prepare for future job interviews. As I conquer algo challenges, I plan to use Dev and Medium as my digital rubber ducks. Here's a classic "Two Sum" problem that is commonly seen in job interviews:
Coding Challenge:
Write a function that takes in a non-empty array of integers and an integer representing a target sum. The function should return the two numbers that sum up to the target sum. If there are no two numbers that sum up to the target sum, the function should return an empty array. You my assume that each input would have at most one pair, and you may not use the same element twice. Numbers can be returned in any order.
Sample Input
array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10
Sample Output
[-1, 11]
Let's first break down the problem. Our function twoNumSum will take in an array of integers ([3, 5, -4, 8, 11, 1, -1, 6]) and a target sum (10). Our goal is to find two numbers inside our array that add up to the target sum. If we look at our array, numbers -1 and 11 are the only two numbers that add up to 10. The function should then return these two numbers.
There are different ways in which you can solve this problem. We can, of course, solve it by using nested loops (brute force approach) where we iterate over the array twice to find the sum. In other words, we would iterate the array at each number in order to check if adding the number to any other number in the array adds up to the sum. The two for loops approach is an easy solution; however, it isn't an optimal one. Traversing through two for loops will result in a running time of O(n²) , since for each number(array[i]), we have to iterate through the rest of the numbers in the array which runs in O(n) time. It will have a constant space complexity O(1) because we are not creating any temporary storage to store the data. There is a more efficient approach to solving this problem, and that is by using a hash table.
Our hashing approach will result in a faster, more efficient algorithm. We start by creating an empty hash. We will then iterate over the array. As we traverse the array, we have to check if the difference between the current number (array[i]) and the targetSum (in this case it is 10) is found in our hash table. In order to do that, we will create a new variable and call it possibleMatch which would be equal to targetSum-array[i]. If it is found in our hash, then we will return the possibleMatch and our current number (array[i]). In the case where our possibleMatch number isn't found in the hash table, we will then store the number in our hash. This will run in linear O(n) time complexity, since we only need to loop through the array once. Look up in the hash table runs in constant time O(1). However, since we're creating a temporary storage (hash = {}), the space complexity will increase to O(n).
To solve this problem in Ruby, we follow the same logic.
Hashing technique is considered a 'good' solution, but it is not the best one. There are other, more efficient ways to solve this problem. Perhaps I'll leave it for another post.
Source:
AlgoExpert.io, Leet Code
Top comments (0)