2 Sum Problem is a very famous and classic interview question. In this, we must find two numbers in an array whose sum equals the target number.
This might sound easy, but implementing it efficiently can be an overhead. There is more than one way to solve this problem, and we will see the two best ways to solve the 2 Sum Problem in Java.
Before Jumping out to the solution, let’s understand the questions, and how they will be asked in coding interviews.
Given Numbers {0, 5, 10, 15, 20} and target = 15
Output will be [1, 2], [0, 3]
Because number[1] + number[2] = 5 + 10 = 15
similarly number [0, 3] = 0 + 15 = 15
Beginners Approach
I am calling it the beginner approach because it does not require advanced Java concepts and DSA like Hashmap. You can solve this problem by using basic array operations.
class TwoSum { } Output Enter the Target number: 15 Explanation: There is not much to explain, it is very simple and easy to understand after all. Only the hard part is nested for loop and what is happening inside the loop. You might also wonder how many iterations it performs during the program execution. Let’s talk about these key points in detail. for (int i = 0; i < array.length; i++) { if (target == array[i] + array[j]) { Time Complexity: O(n²) Advanced Approach In this method, we are going to use the Hashmap. This method will drastically decrease the time complexity from O(n²) to O(n). public class TwoSum { }
import java.io.*;
static void arr(int[] array, int target){ for (int i = 0; i < array.length; i++){
for (int j = i + 1; j < array.length; j++){
if (target == array[i] + array[j]){
System.out.println("[" + i + "," + j + "] = " + target);
}
}
}
}
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
System.out.print("Enter the Target number: ");
int target=Integer.parseInt(br.readLine());
System.out.print("Enter the n: ");
int n = Integer.parseInt(br.readLine());
int[] array = new int[n];
for (int i = 0; i < array.length; i++){
System.out.print("Enter the array element for index:"+i+" ");
array[i] = Integer.parseInt(br.readLine());
}
arr(array, target);
} catch (Exception e) {
System.out.println("Error: " + e);
}
}
Enter the n: 4
Enter the array element for index:0 0
Enter the array element for index:1 5
Enter the array element for index:2 10
Enter the array element for index:3 15
[0,3] = 15
[1,2] = 15
for (int j = i + 1; j < array.length; j++) {
System.out.println("[" + i + "," + j + "] = " + target);
}
In the above code, it checks whether the sum of two paired elements is equal to the target value. If it is, the code prints the indices where it found these elements.
Space Complexity: O(n)
import java.util.HashMap;
public static int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{i, map.get(complement)};
} else {
map.put(nums[i], i);
}
}
return null;
}
public static void main(String[] args) {
int[] nums = new int[]{2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
if (result != null) {
System.out.println("The indices of the two numbers that add up to " + target + " are " + result[0] + " and " + result[1]);
} else {
System.out.println("No two numbers in the array add up to " + target);
}
}