2 ways to Two Sum

Question: Given an array A and a target T, check if there exists a pair in A which sum to T.

If you're starting out on you're interview prep journey, this is usually the first one you encounter.

Let's break it down. 
What is the question asking us to do?

1. We're given an array, that array could be sorted or unsorted. Let A[] = [2,5,1,6,8,3,4,7]
2. We're given a target T= 15
3. We've to return check if there exists a pair which sum to t, ie let x & y be two elements in A such that x+y = T. We have to find those two elements.

Naive/ Brute force approach :
Brute force approach would be to search for each x & y pairs which would sum to target T:

public class Solution {

  //brute force O(n^2) time O(1) space
  public int[] twoSum(int[] nums,int target){
    for(int i=0;i<nums.length-1;i++){
      for(int j=i;j<nums.length;j++){
        if(nums[i]+nums[j] == target) return new int[]{i,j};
      }
    }
    return new int[]{-1,-1};
  }

This will generate all the possible pairs and it will return the first pair which matches the condition, now let's consider a case where give array is

A = [1,2,3,4,5,6,7,8] Target = 15

In this case all the possible combination from [1,2],[1,3],[1,4],[1,5]..[7,8] will be generated.

Improvement :
Let's think about what do we have at our disposal, how can we manipulate the array such that it reduces the time now in the previous worst-case scenario, worst case occurs when we've to search the entire array and the result is located at the last ie[7,8]?

1. Sorting and Two pointers: if we sort the array A, then A becomes [1,2,3,4,5,6,7,8]. How can we use this to our advantage? let's assign two pointers, start and end. start = 0 & end = nums.length-1; here we observe that if
   1. nums[start] + nums[end] == target, we've reached the solution.
   2. nums[start] + nums[end] > target, we've too much of the bigger number, so decrement end.
   3. nums[start] + nums[end] < target, we've too less of the smaller number, so increment start. But here we face a caveat since we're expected to return the indices of the elements in the array. For that we do:
   4. search for the start and end elements in the array.

int[] nums2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(nums2);
            int a = 0, b = 0;
            int start = 0, end = nums2.length-1;
            //find two nums
            while(start<end){
                int sum = nums2[start] + nums2[end];
                if(sum < target)
                    start++;
                else if(sum > target)
                    end--;
                else{
                    a = nums2[start]; b = nums2[end];
                    break;
                }
            }
            //find the index of two numbers
            int[] res = new int[2];
            for(int i = 0; i < nums.length; i++){
                if(nums[i] == a){
                    res[0] = i;
                    break;
                }
            }
            if(a != b){
                for(int i = 0; i < nums.length; i++){
                    if(nums[i] == b){
                        res[1] = i;
                        break;
                    }
                }
            } else{
                for(int i = 0; i < nums.length; i++){
                    if(nums[i] == b && i != res[0]){
                        res[1] = i;
                        break;
                    }
                }
            }

            return res;
}

At this point, the interviewer should be happy with you're approaching but he'll ask
"can we do better?"
And yes we can.

1. HashMap: HashMap store pairs, we use this property to store the index and the sum. We store target-num[i] as key and the index i as value. Let go through it: for array [2,5,1,6,8,3,4,7] and target = 15, the key value pairs stored are:

2 > 15-2 = 13 <13,0>
5 > 15-5 = 10 <10,1>
1 > 15-1 = 14 <14,2>
6 > 15-6 = 9  < 6,3>
8 > 15-8 = 7  < 7,4>
3 > 15-3 = 12 <12,5>
4 > 15-4 = 11 <11,6>

7 > now here is where the magic happens, since at index 4, element 8, we stored <7,4> in hashMap, it means that we need that and we've seen 15-7 = 8 at position 4. which means we've found the solution. return the current index of 7 ie 7 and index of 8 ie 4.

 Map<Integer,Integer> map = new HashMap<>();
        int[] res = new int[]{-1,-1};
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                res[1] = i;
                res[0] = map.get(nums[i]);
            }else{
                map.put(target-nums[i],i);
            }
        }
        return res;
 }

Hope you enjoyed the ride.
Github link : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/TwoSum.java