We have been given two sorted arrays and a number K . We have to merge the two sorted arrays in the sorted manner and return the element at the Kth position.
- My approach is to use two variables which will tell us where are we in the two arrays.
- Start comparing arr1[arr1_index] with arr2[arr2_index] and see who is smaller.
- Now , Start a loop with the smaller element and move forward to see if there are other elements following the smaller element which are smaller than the greater of the two values , we just compared in the previous step.
- Write those values in a new array and following them write the greater value in that array too.
- If we come across duplicates then doubly write them one after the other.
- after merging both , return[K+1] element of the combined array
I have done it myself and am wondering if there is an more efficient approach to it, and if you know then please describe it in a beginner-friendly language.
It contains a lot of console output statements, thought that it would ease the reviewers :)
public class TwoSortedArraysKthElement {
static int KthElementInTwoArrays(int[] arr1,int arr1_length, int[] arr2, int arr2_length,int k){
int[] new_arr = new int[arr1_length+arr2_length];
int lastIndexOfNewArr = -1;
int arr1_loop_index = 0;
int arr2_loop_index = 0;
while (arr1_loop_index < arr1_length && arr2_loop_index < arr2_length) {
for (int i : new_arr) {
System.out.print(i+" ");
}
System.out.println();
System.out.println("LastIndex is "+ lastIndexOfNewArr);
if (arr1[arr1_loop_index] < arr2[arr2_loop_index]) {
int greater_val = arr2[arr2_loop_index];
for (int i = arr1_loop_index; i < arr1_length; i++) {
if (arr1[i] <= greater_val) {
new_arr[lastIndexOfNewArr + 1] = arr1[i];
lastIndexOfNewArr++;
arr1_loop_index++;
System.out.println("LastIndex is "+ lastIndexOfNewArr);
System.out.println("arr1Index is "+ arr1_loop_index);
} else {
break;
}
}
new_arr[lastIndexOfNewArr+1] = greater_val;
lastIndexOfNewArr++;
arr2_loop_index++;
for (int i : new_arr) {
System.out.print(i+" ");
}
System.out.println();
System.out.println("LastIndex is "+ lastIndexOfNewArr);
System.out.println("arr2Index is "+ arr2_loop_index);
} else if (arr1[arr1_loop_index] > arr2[arr2_loop_index]) {
int greater_val = arr1[arr1_loop_index];
for (int i = arr2_loop_index; i < arr2_length; i++) {
if (arr2[i] <= greater_val) {
new_arr[lastIndexOfNewArr + 1] = arr2[i];
lastIndexOfNewArr++;
arr2_loop_index++;
System.out.println("LastIndex is "+ lastIndexOfNewArr);
System.out.println("arr2Index is "+ arr2_loop_index);
} else {
break;
}
}
new_arr[lastIndexOfNewArr+1] = greater_val;
lastIndexOfNewArr++;
arr1_loop_index++;
for (int i : new_arr) {
System.out.print(i+" ");
}
System.out.println();
System.out.println("LastIndex is "+ lastIndexOfNewArr);
System.out.println("arr1Index is "+ arr1_loop_index);
} else {
new_arr[lastIndexOfNewArr+1] = arr1[arr1_loop_index];
arr1_loop_index++;
lastIndexOfNewArr++;
System.out.println("lastindex is "+ lastIndexOfNewArr);
System.out.println("arr1index is "+ arr1_loop_index);
new_arr[lastIndexOfNewArr+1] = arr2[arr2_loop_index];
arr2_loop_index++;
lastIndexOfNewArr++;
System.out.println("lastindex is "+ lastIndexOfNewArr);
System.out.println("arr2index is "+ arr2_loop_index);
}
for (int i : new_arr) {
System.out.print(i+" ");
}
System.out.println();
}
if (arr1_loop_index >= arr1_length) {
for (int i = arr2_loop_index; i < arr2_length;i++) {
new_arr[lastIndexOfNewArr+1] = arr2[i];
lastIndexOfNewArr++;
}
} else if (arr2_loop_index >= arr2_length) {
for (int i = arr1_loop_index; i < arr1_length;i++) {
new_arr[lastIndexOfNewArr+1] = arr1[i];
lastIndexOfNewArr++;
}
}
for (int i : new_arr) {
System.out.print(i+" ");
}
System.out.println();
return new_arr[k+1];
}
public static void main(String[] args) {
int[] arr1 = {1,2,3,5,6};
int[] arr2 = {4,5,6,7,8};
int k = 5;
System.out.println("the element at the kth position is "+KthElementInTwoArrays(arr1,arr1.length,arr2,arr2.length,k));
}
}
