This will be the first installment on a series diving into some of the most popular and utilized coding questions by large technology firms. Many of these challenges were provided by the tech interview handbook. Video explanations and code repositories will be provided at the end of each article. Two Sum may just be one of the most popular coding questions on the entire platform, making it a great starting point since it is not only popular, but also relatively easy to understand.
Problem Description
We are given a method that accepts an integer array called nums and an integer called target. The goal of this problem is to return the indices of two elements in the array that add up to target. It can be assumed that there will be exactly one solution in each test case and that the same element will not be used twice. The answer can be returned in any order.
Example 1:
- Input: nums = [2,7,11,15], target = 9
- Output: [0,1]
- Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
- Input: nums = [3,2,4], target = 6
- Output: [1,2]
Brute Force Solution
The most intuitive and easiest to implement solution takes a brute force approach. Here we will take the index of an array element and compare it against all the consecutive elements ahead of it. Even though this this will give us an answer, it will do so in time complexity O(N^2) because for every number in the array, we will need to compare every other element against that one.
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length - 1; i++) {
for(int j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
return nums;
}Even though this accomplishes the task at had, for extremely large datasets the amount of time to compute these values will increase exponentially. Lets try to find a solution that will solve this in linear time complexity.
HashMap Solution
An alternative to the brute force algorithm is to implement using a HashMap which will hold the value and index of each element in our array (with each key/value pair being added during traversal). The idea behind this solution is to iterate over every element in the array calculate a complement. This complement will be equal to target value minus the current element we are on. By subtracting our current value from the target, we then will know that any number that is left over will have to be a second number that adds up to the target.
We can then check out hash map for this complement and see if is contained as a key. If the complement is contained, then we know that the remaining amount needed to be added to the complement will be nums[i]. This means we have solved our problem and can return the value of the hash map entry, along with our current index position. Otherwise if the complement does not exist, we will just add the current value and index of our loop.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (numMap.containsKey(complement)) {
return new int[] {numMap.get(complement), i};
}
numMap.put(nums[i],i);
}
return nums;
}Using this method, we can guarantee that every element in the array will only need to be accessed exactly one time, resulting in a time complexity of O(N). This solution is substantially more optimal that the brute force approach and will be more impressive to any recruiter that is asking this coding question.
Summary
Being able to solve this question in linear runtime complexity can seem daunting when it is first encountered, but once the basic algorithm and mathematical operations are laid it out becomes relatively simple. It is important to remember determining what two numbers sum to a target is the same concept as finding which two numbers subtracted from that target equal zero.