Two Pointers

Two Number Sum Problem solution in Java

Rajeev SinghAlgorithms1 mins read

Two Sum Problem

Two Number Sum Problem Statement

Given an array of integers, return the indices of the two numbers whose sum is equal to a given target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9.

The output should be [0, 1]. 
Because nums[0] + nums[1] = 2 + 7 = 9.

Two Number Sum Problem solution in Java

METHOD 1. Naive approach: Use two for loops

The naive approach is to just use two nested for loops and check if the sum of any two elements in the array is equal to the given target.

Time complexity: O(n^2)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {

    // Time complexity: O(n^2)
    private static int[] findTwoSum_BruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {};
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] nums = new int[n];

        for(int i = 0; i < n; i++) {
            nums[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();

        keyboard.close();

        int[] indices = findTwoSum_BruteForce(nums, target);

        if (indices.length == 2) {
            System.out.println(indices[0] + " " + indices[1]);
        } else {
            System.out.println("No solution found!");
        }
    }
}
# Output
$ javac TwoSum.java
$ java TwoSum
4 2 7 11 15
9
0 1

METHOD 2. Use a HashMap (Most efficient)

You can use a HashMap to solve the problem in O(n) time complexity. Here are the steps:

  1. Initialize an empty HashMap.
  2. Iterate over the elements of the array.
  3. For every element in the array -
    • If the element exists in the Map, then check if it’s complement (target - element) also exists in the Map or not. If the complement exists then return the indices of the current element and the complement.
    • Otherwise, put the element in the Map, and move to the next iteration.

Time complexity: O(n)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {
    
    // Time complexity: O(n)
    private static int[] findTwoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
    }
}

METHOD 3. Use Sorting along with the two-pointer approach

There is another approach which works when you need to return the numbers instead of their indexes. Here is how it works:

  1. Sort the array.
  2. Initialize two variables, one pointing to the beginning of the array (left) and another pointing to the end of the array (right).
  3. Loop until left < right, and for each iteration
    • if arr[left] + arr[right] == target, then return the indices.
    • if arr[left] + arr[right] < target, increment the left index.
    • else, decrement the right index.

This approach is called the two-pointer approach. It is a very common pattern for solving array related problems.

Time complexity: O(n*log(n))

import java.util.Scanner;
import java.util.Arrays;

class TwoSum {

    // Time complexity: O(n*log(n))
    private static int[] findTwoSum_Sorting(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] + nums[right] == target) {
                return new int[] {nums[left], nums[right]};
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {};
    }
}