CC-12 : Find element at position k, when two sorted arrays are merged.

Description:

Given two sorted input integer arrays arr1 and arr2, and integer k, find and return the element at position k, when the two input arrays are merged.

Test cases and expected outputs:

Input Parameters	Expected outputs
arr1={1,3,5,7} arr2={2,4} k=4	Merged array={1,2,3,4,5,7}. The 4th element of merged array is 4.
arr1={-3,-2,-1,0,1,2,3} arr2={0,0} k=5	Merged array={-3,-2,-1,0,0,0,1,2,3}. The 5th element of merged array is 0.
arr1={4,5} arr2={1,2,9,12} k=3	Merged array={1,2,4,5,9,12}. The 3th element of merged array is 4.

Pseudocode:

The java method should accept following input parameters: arr1(sorted int array), arr2(sorted int array), int k.

Initialize int array arr3 with length=arr1.length+arr2.length.

Initialize int variables arr1Idx and arr2Idx to 0.

Iterate through arr3 indices from 0 to arr3.length-1 using a while loop with loop variable arr3Idx:

If (arr1[arr1Idx]<=arr2[arr2Idx]) and arr1Idx< arr1.length and arr2Idx< arr2.length:

Add arr1[arr1Idx] to arr3[arr3Idx].

Increment arr1Idx by 1 and arrIdx3 by 1.

If (arr1[arr1Idx]>arr2[arr2Idx]) and arr1Idx< arr1.length and arr2Idx< arr2.length:

Add arr2[arr2Idx] to arr3[arr3Idx].

Increment arr2Idx by 1 and arrIdx3 by 1.

After above while loop is complete, arr3 will have the merged array, return arr3 and arr3[k-1] (element at kth position) using a multidimensional int array.

Code:

public int[][] arrayFindElementAtPositionK(int[] arr1, int[] arr2, int k) throws Exception{
	int arr3[] = new int[arr1.length+arr2.length];
	int arr1Idx=0;	int arr2Idx=0;
	int arr3Idx=0;
	while (arr3Idx < arr3.length) {
		if ((arr2Idx< arr2.length)&&((arr1Idx==arr1.length)||(arr2[arr2Idx]<=arr1[arr1Idx]))){
			arr3[arr3Idx]=arr2[arr2Idx];
			arr2Idx++;
			arr3Idx++;
			continue;
		}
		if ((arr1Idx< arr1.length)&&((arr2Idx==arr2.length)||(arr1[arr1Idx]<=arr2[arr2Idx]))){
			arr3[arr3Idx]=arr1[arr1Idx];
			arr1Idx++;
			arr3Idx++;
			continue;
		}
	}
	int[][] retArr=new int[2][];
	retArr[0]=new int[1];
	retArr[0][0]=arr3[k-1];
	retArr[1]=arr3;
	return retArr;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class ArrayFindElementAtPositionK {
	
public int[][] arrayFindElementAtPositionK(int[] arr1, int[] arr2, int k) throws Exception{
	int arr3[] = new int[arr1.length+arr2.length];
	int arr1Idx=0;	int arr2Idx=0;
	int arr3Idx=0;
	while (arr3Idx < arr3.length) {
		if ((arr2Idx< arr2.length)&&((arr1Idx==arr1.length)||(arr2[arr2Idx]<=arr1[arr1Idx]))){
			arr3[arr3Idx]=arr2[arr2Idx];
			arr2Idx++;
			arr3Idx++;
			continue;
		}
		if ((arr1Idx< arr1.length)&&((arr2Idx==arr2.length)||(arr1[arr1Idx]<=arr2[arr2Idx]))){
			arr3[arr3Idx]=arr1[arr1Idx];
			arr1Idx++;
			arr3Idx++;
			continue;
		}
	}
	int[][] retArr=new int[2][];
	retArr[0]=new int[1];
	retArr[0][0]=arr3[k-1];
	retArr[1]=arr3;
	return retArr;
}

	
public static void main(String[] args) {
	ArrayFindElementAtPositionK ap= new ArrayFindElementAtPositionK();
	int retVal[][];
	try {
	int[] intArray1 = {1,3,5,7};
	int[] intArray2 = {2,4};
	int k=4;
	printArraySummary(intArray1, "Original Array1");
	printArraySummary(intArray2, "Original Array2");
	retVal=ap.arrayFindElementAtPositionK(intArray1, intArray2,k );
	System.out.println("4th element of merged array: "+retVal[0][0]);
			
	int[] intArray4 = {-3,-2,-1,0,1,2,3};
	int[] intArray5= {0,0};
	k=5;
	printArraySummary(intArray4, "Original Array1");
	printArraySummary(intArray5, "Original Array2");
	retVal=ap.arrayFindElementAtPositionK(intArray4, intArray5,k );
	System.out.println("5th element of merged array: "+retVal[0][0]);
			
	int[] intArray7 = {4,5};
	int[] intArray8 = {1,2,9,12};
	k=3;
	printArraySummary(intArray7, "Original Array1");
	printArraySummary(intArray8, "Original Array2");
	retVal=ap.arrayFindElementAtPositionK(intArray7, intArray8,k );
	System.out.println("3rd element of merged array: "+retVal[0][0]);
			
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
				
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}
	

}