find all pairs in an array, that sum up to particular number with best complexity

Here we discuss two possible algorithms

• algorithm with the time complexity O(n) and with no additional space complexity
• algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)
• brute force algorithm with time complexity of O(n^2)

Algorithm with the time complexity O(n) and with no additional space complexity

        /**
	 * Find the pair in an array whose sum with complexity O(n). This assumes
	 * the array passed is sorted array and there are no duplicates in the array
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 */
	public void getPair2(int[] arr, int k) {
		int start = 0;
		int end = arr.length - 1;
		int sum = 0;

		// output array to record matching pairs
		StringBuilder arrs = new StringBuilder();

		while (start < end) {
			sum = arr[start] + arr[end];
			if (sum == k) {
				// we have found one pair, add it to our output array
				arrs.append(arr[start] + "," + arr[end] + ";");
				start++;
				end--;
			} else if (sum < k) {
				// if the sum of the pair is less than the sum we are searching
				// then increment the start pointer which would give us the sum
				// more than our current sum as the array is sorted
				start++;
			} else {
				// if the sum of the pair is greater than the sum we are searching
				// then decrement the end pointer which would give us the sum
				// less than our current sum as the array is sorted
				end--;
			}
		}
		System.out.println(arrs.toString());
	}

Output: 1,5;2,4;

Algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)

/**
	 * Find the pair in an array whose sum with complexity O(2n)
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 * @return string of combination of array pairs
	 */
	public String getPair(int[] arr, int k) {
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		String result = "";

		/**
		 * First store array elements into hashmap with key as the value of the
		 * array This has time complexity of O(n) and space complexity of O(n)
		 */
		for (int i = 0; i < arr.length; i++) {
			hm.put(arr[i], arr[i]);
		}

		/**
		 * Try getting the hashmap value at key (sum-array_element) If it
		 * exists, it means array_element and sum-array_element is the pair
		 * thats forms sum 'k' This has time complexity of O(n)
		 */
		for (int i = 0; i < arr.length; i++) {
			if (hm.get(k - arr[i]) != null) {
				result += arr[i] + "," + (k - arr[i]) + ";";
			}
		}
		return result;
	}

Output: Pair of elements at O(2n) time complexity and O(n) space complexity: 4,2;2,4;5,1;1,5;

Brute force algorithm with time complexity of O(n^2)

/**
	 * Find the pair in an array whose sum with complexity O(n^2)
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 * @return string of combination of array pairs
	 */
	public String findPair(int[] arr, int k) {
		int i = 0, j = arr.length - 1;
		String result = "";
		while (i < j) {
			while (i < j) {
				if (arr[i] + arr[j] == k) {
					result += arr[i] + "," + arr[j] + ";";
				}
				j--;
			}
			i++;
			j = arr.length - 1;
		}
		return result;
	}

Output: Pair of elements at O(n^2) time complexity and no additional space complexity: 4,2;5,1;