Two Sum Problem

 Given an array of size N and an integer 'target'. Find the indices (i, j) of two numbers such that their sum is equal to target. (i != j). Assume there is only one solution.

array = [11, 7,3, 9, 14, 2] and target = 17

Brut force approach, time complexity will be O(n2) as we need to consider all the pairs  (check an element with other elements in the array). But the space complexity remains constant O(1).

Optimisation: Instead of checking an element with all other element, we need to find the difference between the target and the element and check the difference value is present in the array.

eg 17 - 11 = 6 and we need to check whether 6 is present in the array. 

For this a Hashmap is used with index and integer and before adding the element in the Hashmap check the difference value is present in it.

public class TwoSumProblem {
    public static void main(String[] args) {
        int[] arr = {11, 3,7,9,14,2};
        int target = 17;
        int[] ans = new int[2];

        HashMap<Integer, Integer> map = new HashMap<>();
        int i = 0;
        for (int value: arr) {
           
            // say 11 is the first element then secondValue is 17 - 11 = 6
            int secondValue = target - value;
            if (map.containsValue(secondValue)) {
                ans[0] = map.get(secondValue);
                ans[1] = i;
                break;
            }
            map.put(value, i);
            i++;
        }
        System.out.println(ans[0] + " "+ans[1]);
    }
}