Interview Question Two Sum

Solution by Fatih KABAKCI

The problem is finding a sub array which has indices of two elements in an array that if adding of corresponding their values equals a specific value. The following problem has been published on LeetCode.com. The basic one of the solution has been provided below.

Problem #1 - Two Sum

Description: Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy;

import java.util.Scanner;

/**
 * 
 * @author fkabakci
 * Problem Description: Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * 
 * Examples:
 * 
 * Given nums = [2, 7, 11, 15], target = 9,

   Because nums[0] + nums[1] = 2 + 7 = 9,
   return [0, 1].
   
   Given nums = [0, 4, 3, 2, 0], target = 0,
   return [0, 4].
   
   Solution:
   
   Basic one,
   Brute Force Approach
 */

public class TwoSum {
	public static int[] twoSum(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 null;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("Please input an array size");
		int n = in.nextInt();
		int[] nums = new int[n];
		System.out.println("Please fill up the array");
		for (int i = 0; i < n; i++) {
			nums[i] = in.nextInt();
		}
		System.out.println("Please input a target");
		int target = in.nextInt();

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

		if (indices != null)
			System.out.println("[" + indices[0] + "," + indices[1] + "]");
		else
			System.out.println("There are no couple of indices in the array that sum of them equals the target.");
	}
}

We try every possible each two elements of the array by adding one another to reach target by brute force approaching in the Java program above. Then, we return the array or null in regard to whether we could find two indices. The algorithm time complexity is O(n^2) because we travel for each element in two loops.