Jan 26
Ace Your Next Coding Interview: Solving the Two Sum Problem
Hello everyone, I am a software developer with 7 years of experience in backend development. Throughout my career, I have had the opportunity to work at some of the top product-based companies in the world. In this blog post, I am excited to share my insights on one of the most common interview questions for software developers, the Two Sum problem.
This is the first post in my series “Ace Your Next Coding Interview” posts where I will be discussing popular DSA (Data Structures and Algorithm) interview questions. I will be providing various approaches to solving these problems and providing code examples in Java. Whether you are a beginner or an experienced developer, I hope you find this information useful in your journey to becoming a better programmer and ace your next DSA interview.
Two sum Problem
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer 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]Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Brute-force Solution
The brute force solution for the Two Sum problem involves checking all possible pairs of integers in the input array to see if they add up to the target sum. To implement this solution, we can use two nested loops. The outer loop iterates through all elements of the input array, and the inner loop iterates through all the remaining elements of the input array. For each pair of integers, we check if they add up to the target sum. If they do, we return an array containing the indices of these integers.
Here is an example of the brute force solution implemented in Java:
class Solution {
public int[] twoSum(int[] nums, int target) {
// Iterate through all elements of the input array
for (int i = 0; i < nums.length; i++) {
// Iterate through all remaining elements of the input array
for (int j = i + 1; j < nums.length; j++) {
// Check if the current pair of integers add up to the target sum
if (nums[i] + nums[j] == target) {
// Return an array containing the indices of these integers
return new int[]{i, j};
}
}
}
// If no pair of integers adds up to the target sum, return null
return null;
}
}The time complexity of the brute force solution is O(n²) where n is the size of the input array. This is because we are using two nested loops, each iterating through the input array. The space complexity of the brute force solution is O(1) as we are not using any additional data structures.
The brute force solution is a simple approach to solve the Two Sum problem, but it has a poor time complexity. It can be slow for large input arrays and is not recommended for use in real-world applications where performance is a concern.
HashMap Solution
An efficient solution to the Two Sum problem is to use a HashMap. The idea is to store the elements of the input array as keys and their indices as values in the HashMap. Then, for each element in the input array, we check if the HashMap contains the key that is equal to the target sum minus the current element. If it does, we return the values (indices) associated with the current element and the key in the HashMap.
Here is an example of the HashMap solution implemented in Java:
class Solution {
public int[] twoSum(int[] nums, int target) {
// create a HashMap to store the elements of the input array as keys and their indices as values
Map<Integer, Integer> indexMap = new HashMap<>();
// add the first element of the input array to the map with the index 0
indexMap.put(nums[0], 0);
for(int i=1;i<nums.length;i++) {
// check if the HashMap contains the key that is the target value minus the current element
if(indexMap.containsKey(target- nums[i])){
// if it does, it means that the current element and the corresponding value found in the map add up to the target value
int[] answer = new int[2];
// assign the index of the current element and the corresponding value found in the map to the array
answer[0] = indexMap.get(target- nums[i]);
answer[1] = i;
return answer;
}
// add the current element and its index to the map
indexMap.put(nums[i], i);
}
return null;
}
}The time complexity of the HashMap solution is O(n) where n is the size of the input array. This is because we are iterating through the input array once and for each element, the time complexity of getting or putting an element in a HashMap is O(1) on average. The space complexity of the HashMap solution is also O(n) as we are storing n elements in the HashMap.
2-Pointer based Approach
The 2-pointer based approach is another efficient solution for solving the Two Sum problem. This approach utilizes two pointers, one pointing to the first element of the input array and the other pointing to the last element. The idea is to sort the input array first and then use the two pointers to iterate through the array and check if the current pair of integers add up to the target sum. If they do, we return an array containing the indices of these integers. If the sum of the current pair of integers is less than the target sum, we move the left pointer to the next element. If the sum of the current pair of integers is greater than the target sum, we move the right pointer to the previous element.
Here is an example of the 2-pointer based approach implemented in Java:
class Solution {
public int[] twoSum(int[] nums, int target) {
// Sort the input array
Arrays.sort(nums);
// Declare two pointers, one pointing to the first element of the input array and the other pointing to the last element
int left = 0, right = nums.length - 1;
// Iterate through the input array using the two pointers
while (left < right) {
// Check if the current pair of integers add up to the target sum
if (nums[left] + nums[right] == target) {
// Return an array containing the indices of these integers
return new int[]{left, right};
}
// If the sum of the current pair of integers is less than the target sum, move the left pointer to the next element
else if (nums[left] + nums[right] < target) {
left++;
}
// If the sum of the current pair of integers is greater than the target sum, move the right pointer to the previous element
else {
right--;
}
}
// If no pair of integers adds up to the target sum, return null
return null;
}
}The time complexity of the 2-pointer based approach is O(n log n) where n is the size of the input array. This is because we are sorting the input array first which takes O(n log n) time. The space complexity of the 2-pointer based approach is O(1) as we are not using
The space complexity of the 2-pointer based approach is O(1) as we are not using any additional data structures, and we are only using two pointers which only take a constant amount of space.
It is important to note that this approach requires the input array to be sorted, which means that the original indices of the elements in the input array will be lost. Therefore, this approach may not be suitable in cases where the original indices of the elements are needed.
Common Mistakes
These are some common mistakes candidates make when they get Two sum question in the interview.
- Not considering edge cases: One of the most common mistakes people make when solving the Two Sum problem is not considering edge cases. For example, not considering the possibility of negative numbers in the input array or not handling the case where no pair of integers adds up to the target sum.
- Not paying attention to the problem constraints: Another common mistake is not paying attention to the problem constraints. For example, not considering the fact that each input would have exactly one solution and not using the same element twice.
- Not understanding the time and space complexity requirements: People often choose an approach that they are comfortable with, without considering the time and space complexity requirements of the problem. It is important to choose an approach that is efficient in terms of time and space complexity, especially when solving interview questions.
- Not using proper data structures: The Two Sum problem can be solved using different data structures like arrays, linked list, HashMap and more. Not using the right data structures can lead to poor performance and inefficiency.
Conclusion
In conclusion, the Two Sum problem is a common problem in the field of computer science that can be solved using various approaches. In this post, we have discussed three different solutions to the Two Sum problem using Java: the brute force solution, the HashMap solution, and the 2-pointer based approach.
The brute force solution is a simple approach to solve the problem, but it has a poor time complexity and is not recommended for use in real-world applications where performance is a concern.
The HashMap solution is an efficient solution that utilizes a HashMap data structure to store the elements of the input array as keys and their indices as values. It has a good time and space complexity, and it is easy to understand and implement.
The 2-pointer based approach is also an efficient solution that utilizes two pointers and sorting to solve the problem. It has a good space complexity but a slightly less efficient time complexity than the HashMap solution.
Overall, both HashMap and 2-pointer based approach are efficient solutions for solving the Two Sum problem, and it depends on the specific use case and requirement which one to use. It is important to consider the trade-offs between time and space complexity when choosing the right approach for a given problem.
I hope you found this post informative and useful. Stay tuned for more DSA interview question blog posts in the series. Follow me for more updates and insights on popular DSA interview questions or engineering mentorship.
To learn more about Ace Your Next Coding Interview series, checkout https://sde-mentor.medium.com/list/ace-your-next-coding-interview-series-a847a9d1e57f
To learn more about mentorship, Checkout my mentorship series here: https://medium.com/@sde-mentor/list/mentorship-series-be62191a4c87
