# 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

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 = 9Output: [0,1]Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].`

Example 2:

`Input: nums = [3,2,4], target = 6Output: [1,2]`

Example 3:

`Input: nums = [3,3], target = 6Output: [0,1]`

# Brute-force Solution

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

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

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

1. 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.
2. 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.
3. 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.
4. 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

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.

--

--

## More from Krunal Parmar

I'm a software dev with 7 years exp.I am Passionate about mentoring, writing on mentorship, tech & career development here.

## Get the Medium app

I'm a software dev with 7 years exp.I am Passionate about mentoring, writing on mentorship, tech & career development here.