2 Sum All Pair II

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

Assumptions

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

• The order of the values in the pair does not matter

Examples

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

Solution: Sort then left right pinch, or hashmap

public class Solution {
  public List<List<Integer>> allPairs(int[] array, int target) {
    Arrays.sort(array);
    List<List<Integer>> result = new ArrayList<>();
    int left = 0;
    int right = array.length - 1;
    while (left < right){
      if ( left > 0 && array[left] == array[left - 1]){
        left++;
        continue; //ignore duplicates
      }

      int cur = array[left] + array[right];
      if (cur == target){
        result.add(Arrays.asList(array[left], array[right]));
        left++;
        right--;
      } else if( cur > target){
        right--;
      } else {
        left++;
      }
    }
    return result;
  }
}

public class Solution {
  public List<List<Integer>> allPairs(int[] array, int target) {
      List<List<Integer>> result = new ArrayList<>();

      Map<Integer, Integer> map = new HashMap<>();
      for (int num: array){
        Integer count = map.get(num);
        if (num * 2 == target && count != null && count == 1){ 
          //if one of num already exists within hashmap
          result.add(Arrays.asList(num, num));
        } else if (map.containsKey(target - num) && count == null){
          //if none of num exists, this pair will not be duplicate
          result.add(Arrays.asList(target-num, num));
        }

        if (count == null){
          map.put(num,1);
        } else {
          map.put(num, count + 1);
        }
      }
      return result;
  }
}

Time Comp:

sort, then left right pinch: O(NlogN) sort + O(N) left to right = O(NlogN)

hashmap: O(N) traversal * O(1) map.containskey * O(1) map.put = *O(N)

Space Comp:

sort, then left right pinch: O(1)

hashMap: O(N) hashmap