2 Sum All Pair I

Find all pairs of elements in a given array that sum to the given target number. Return all the pairs of indices.

Assumptions

• The given array is not null and has length of at least 2.

Examples

• A = {1, 3, 2, 4}, target = 5, return [[0, 3], [1, 2]]

• A = {1, 2, 2, 4}, target = 6, return [[1, 3], [2, 3]]

Solution: HashMap

Use hashmap to track indices of values

Iterate through array, if (target - current index value) exists within the map. Add (Current index, other indices) into result.

public List<List<Integer>> allPairs(int[] array, int target){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Map<Integer, List<Integer>> map = new HashSet<Integer, List<Integer>>();
    
    for (int i = 0; i < array.length; i++){
        //get other half of pair
        List<Integer>indices = map.get(target - array[i]);
        
        if (indices != null){
            for (int j: indices){
                results.add(Arrays.asList(j, i); //add pair to result
            {
        }
        
        if (!map.containsKey(array[i])){ // if value at current index not in map
            map.put(array[i], new ArrayList<Integer>()); // make new slot to store indices for current value
        }
        map.get(array[i]).add(i); // add current index
    }
    return result;
}

Time Comp: O(N) when hashmap is empty, approaches O(N^2) near the end.

Space Comp: O(N^2) worst case if every element included in result.