algorithm to merge two sorted arrays without additional array

Algorithm to merge two sorted arrays: Here we use merge sort logic but with a small change; we take the larger size array and start inserting elements from end of that array.

package algorithms.sort;

/**
 * Algorithm to merge two sorted arrays without additional array,
 * provided one of the two arrays has the size of the combination
 * sizes of two arrays
 *
 * @author ntallapa
 *
 */
public class Merge2SortedArraysWO3rdArray {

	public void mergeArrays(int[] aArr, int aSize, int[] bArr, int bSize) {
		// pointer to end of the first sorted array
		int aIdx=aArr.length-1;
		// pointer to end of the second sorted array (pointer at 100 in below array bArr)
		int bIdx=bArr.length-aArr.length-1;
		// pointer to end of the second sorted array (pointer at last 0)
		int cIdx=bArr.length-1;

		/**
		 * whichever is higher in two arrays, place that
		 * element in last position of the bigger array
		 */
		while(cIdx>=0 && aIdx>=0 && bIdx>=0) {
			if(aArr[aIdx] > bArr[bIdx]) {
				bArr[cIdx--] = aArr[aIdx--];
			} else {
				bArr[cIdx--] = bArr[bIdx--];
			}
		}

		// run through the left over elements of array aArr
		while(aIdx>=0) {
			bArr[cIdx--] = aArr[aIdx--];
		}

		// run through the left over elements of array bArr
		while(bIdx>0) {
			bArr[cIdx--] = bArr[bIdx--];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Merge2SortedArraysWO3rdArray mergeArrays = new Merge2SortedArraysWO3rdArray();
		int[] aArr = {3,7,12,16};
		int[] bArr = {1,4,9,100,0,0,0,0};

		mergeArrays.mergeArrays(aArr, aArr.length, bArr, bArr.length);

		for(int i: bArr) {
			System.out.println(i);
		}
	}
}

Output:

1 3 4 7 9 12 16 100

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;

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey