2 Sum Problem Java Solution: A Complete Guide

in java •  last year 

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.

import java.io.*;

class TwoSum {
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);
    }
}

}

Output

Enter the Target number: 15
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

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++) {
for (int j = i + 1; j < array.length; j++) {

if (target == array[i] + array[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.

Time Complexity: O(n²)
Space 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).


import java.util.HashMap;

public class TwoSum {

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);
    }
}

}

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!