javinpaulDisclosure: This post includes affiliate links; I may receive compensation if you purchase products or services from the different links provided in this article.
Hello Devs, if you have been solving data structure and algorithms problems or been through a couple of coding interviews then you might be familiar with the classical "Two Sum" problem.
It's one of the classical coding problems of finding two numbers in a given array whose sum is equal to a given target number. It's a good problem to learn how array data structure works and programming basics like loops, conditionals, and operators.
It's also good for developing your problem-solving skills and coding sense, which will help you in the long run. This is also a popular leetcode problem and commonly asked on coding interviews to both beginners and intermediate programmers.
In this article, I will show you the simplest possible solution to for this problem to kick-start your journey on solving array-based coding problems. Before we talk about the solution, let's revisit the problem statement again:
Problem Statement:
Given an array of integers, find two numbers such that they add up to a specific target number.
The method twoSum(int[] input, target)should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
Note: You may assume that each input would have exactly one solution.
Example
[12,17,21,25], 29 -> [1,2]
In order to solve this problem, a basic knowledge of array data structure and algorithms is experienced. You should also be familiar with Big O notation to calculate time and space complexity.
If you are new to Data Structure and need a course to refresh your knowledge, I highly recommend you check out Data Structures and Algorithms: Deep Dive Using Java to build a foundation. This is a good course to learn data structure and algorithms using Java programming language.
How to solve Two Sum Problem in Java
Here is our complete solution of two sum array problem in Java. This is a brute force way to solve the problem where we start with the first element in the array and then check all other numbers in the array to find the pairs which add to the target value.
This is not the most efficient way to solve this problem but it works and that should be your first goal in the interview as well as in real-life scenarios.
First, solve the problem and then optimize it.
The time complexity of this solution is quadratic O(N²) and if you are asked this problem during the interview then you should also know tricks to reduce time complexity which I have left as an exercise for you.
Good knowledge of data structure, algorithms, and common coding patterns helps you to find alternative solutions and reduce the time complexity. And, that's why I highly recommend every programmer to go through Grokking the Coding Interview: Patterns for Coding Questions course on Educative.
This is one of its kind courses that teaches you some common coding patterns like sliding window, merge interval, fast and slow pointers, two points, and many others which can be used to solve hundreds of coding problems. If you are preparing for coding interviews, I highly recommend you to learn these patterns.
You can either buy this course or you can get an Educative subscription on $18 per month which provides access to many useful courses for coding interviews like Grokking the System Design Interview and Grokking the Dynamic Programming Patterns. I highly recommend this subscription to the programmer preparing for job interviews.
By the way, I have also written unit tests to test the logic in our code but I haven't tested for all scenarios.
You can add more test in given JUnit function and test that if our solution works on boundary conditions like an array with zero elements, array with no pair for a sum, an array with two pairs of given sum, and array with exactly one pair of elements for the given sum.
When you run this program it will run fine and doesn't throw any error because the twoSum() method will return an array with {1, 2} which matches the expected output in the assertArrayEquals() method.
These are actually indices of actual numbers in the input array which adds to the target value.
For example, the target value in our case is 29 and the first and second element (12 + 17) adds to 29. Since the question asked to return indices that are not zero-based we are adding one into indices and returning them.
If you want to play just change the array input or expected output and you will start seeing errors as shown below:
That's all about how to solve two sum problem in Java.This is the brute force way to solve the problem and the time complexity of this problem is O(n²) because of two loops we have in our code. We are checking each element with every other element in the array to find the matching pair.
Can you find a more clever way to solve the problem and reduce the time complexity to O(nlogn) or maybe O(N)?
Other Coding Interview Questions you may like
- 5 Essential Skills to Crack Coding Interviews (skills)
- How to Print duplicate characters from String? (solution)
- How to Find duplicate characters in a String? (solution)
- 50+ Data Structure and Algorithms Interview Questions (list)
- How to Check if String is Palindrome? (solution)
- 30 array-based coding problems from interviews (questions)
- Find the highest occurred character in a String? (solution)
- Check if a String contains only digits? (solution)
- 10 Data Structure and Algorithms courses for Interviews (courses)
- How to reverse String in Java using Iteration and Recursion? (solution)
- Count the occurrence of a given character in String? (solution)
- My favorite free course to learn Data Structure and Algorithms (courses)
- Convert numeric string to an int? (solution)
- Reverse words in a sentence without using a library method? (solution)
- Reverse a String in place in Java? (solution)
- Count the number of vowels and consonants in a String? (solution)
- Find the first non-repeated character from String? (solution)
- 7 Best Data Structure and Algorithms Courses (best courses)
Thanks for reading this article so far. If you like these two sums array-based coding problems then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.
**P. S. --- **If you are preparing for a Programming Job Interview and you need more such questions, you can check the Master the Coding Interview: Data Structures + Algorithms by Andrei Neagoie on Udemy. This is a great course to build and level up your Data Structure and Algorithms skills and crack the coding interview
