Problem Statement

Given an array of integers, find out two indices such that the sum of the numbers at that indices matches K.
For example, {4, 6, 8, 1, 9} and K = 15, the output would be [1,4]

Solution Explanation

The questions is rather simple and is one of the most frequently asked interview questions ever.

Given an integer array, finding two numbers which sum up to K can be done in brute force, by checking every array element with every other. You quit, when you find two numbers which sum up to K. The worst case complexity is O(n^2).

Pseudocode for bruteforce

for i=0 to len-1
    for j=1 to len-1
        if(arr[i]+arr[j] == K)
            return i,j

We can also do this in a single pass of the array by using some extra space, a hashmap. The solution involves checking if the difference of K and the current element exists in the map, if it does return those values, else add the new array element to the map.

Pseudocode for single pass solution using hashmap

    Map<Integer,Integer> map;
    for i=0 to len-1
        if(map contains key K-arr[i])
            return i and map.get(arr[k]-i)
        else
            map.put(arr[i],i)

This solution works great and reduces the worst case time complexity by half. Below is the full java implementation for Two Sum problem,

public class TwoSumImpl {
    public static void main(String[] args){
        int[] arr = {4, 6, 8, 1, 9};
        int[] result = new TwoSumImpl().twoSum(arr, 15);
    }
    public int[] twoSum(int[] nums, int target) {
      Map<Integer,Integer> map = new HashMap<>();
      List<Integer> result = new ArrayList<>();
      for(int i=0;i<nums.length;i++){
          if(map.containsKey(target-nums[i])){
              result.add(i);
              result.add(map.get(target-nums[i]));
              break;
          }else{
              map.put(nums[i],i);
          }
      }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Time Complexity

The time complexity is O(n) and space complexity is O(n).