Find Two Sum / Pair of Sum in list

Problem statement: Given an array of integers, return two numbers such that they add up to a specific target.
e.g. - arr[] = { 4, 6, 5, -10, 8, 5, 20 };
target = 10
Output: [4,6] , [5,5], [-10,20]

Note: You may assume that each input would have exactly one solution, and you may not use the same element twice.

// Method -I:

1. import java.util.HashMap;
2. import java.util.Map;
3. public class PairOfSumByMap {
4. public static void main(String[] args) {
5. int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
6. int num = 10;
7. pairOfSum(arr, num);
8. }
9. public static void pairOfSum(int arr[], int num) {
10. Map<Integer, Integer> map = new HashMap<>();
11. for (int i = 0; i < arr.length; i++) {
12. if (map.containsKey(num - arr[i])) {
13. System.out.println("pair of num: [" + (num - arr[i]) + ", " + arr[i] + "]");
14. } else
15. map.put(arr[i], 0);
16. }
17. }
18. }

Time complexity: O(n) | reason - the array is traversed only once. so the time complexity is directly proportional to the size of the array i.e. O(n)

Space complexity: O(n) | reason -  O(1) + O(n) = O(n).O(1) for the variable and O(n) for the hashmap. for hashmap, with the increase of the number of entries, the hashmap's space will increase linearly. so space complexity of hashmap is O(n).

Output:
pair of num: [4, 6]
pair of num: [5, 5]
pair of num: [-10, 20]

// Method-II: it works only for SORTED arrays

1. import java.util.Arrays;
2. public class PairOfArraySum {
3. static int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
4. public static void main(String[] args) {
5. Arrays.sort(arr); 
6. int i = 0;  // first index
7. int j = arr.length - 1;  // last index
8. while (i < j) {
9. // if arr[i]+arr[j] = num
10. if (arr[i] + arr[j] == 10) {
11. // then print the pair
12. System.out.println("Pair of elements are: (" + arr[i] + "," + arr[j] + ")");
13. i++;  // increment i
14. j--;  // decrement j
15. }
16. // if arr[i]+arr[j]<num
17. else if (arr[i] + arr[j] < 10) {
18. i++;   // then increment i
19. }
20. // if arr[i] + arr[j] >num
21. else if (arr[i] + arr[j] > 10) {
22. j--;  // then decrement j
23. }
24. }
25. }
26. }

Output:

Pair of elements are: (-10,20)

Pair of elements are: (4,6)

Pair of elements are: (5,5)

// Method-III:

1. public class PairOfSumByBruteForce {
2. static int arr[] = { 4, 6, 5, -10, 8, 5, 20 };
3. public static void main(String[] args) {
4. int sum = 10;
5. // brute force
6. for (int i = 0; i < arr.length; i++) {
7. for (int j = i + 1; j < arr.length; j++) {
8. if (arr[i] + arr[j] == sum)
9. System.out.println("Pair of elements are: (" + arr[i] + ", " + arr[j] + ")");
10. }
11. }
12. }
13. }

Output:

Pair of elements are: (4, 6)

Pair of elements are: (5, 5)

Pair of elements are: (-10, 20)

Time complexity: O(n^n)