Problem

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));
}
}
```

Solution

### Length is a property of the array

```
``````
static int KthElementInTwoArrays(int[] arr1,int arr1_length, int[] arr2, int arr2_length,int k){
```

It is unnecessary to pass the array lengths separately. In Java, the length is a property of the array. So `arr1.length`

is the length of that array. You would only need a separate variable if you wanted to work with only part of the array. And in that case, you would probably want to specify the starting index as well.

```
static int kthElementInTwoArrays(int[] a, int[] b, int k) {
```

I also don’t like the name `arr`

in general nor numbered names. I’m not crazy about single letter names, but I would find those better than numbered names.

### More naming

```
``````
int lastIndexOfNewArr = -1;
int arr1_loop_index = 0;
int arr2_loop_index = 0;
```

I would prefer names like

```
int current = 0;
int a_index = 0;
int b_index = 0;
```

But the most common Java standard is to use camelCase, so

```
int current = 0;
int aIndex = 0;
int bIndex = 0;
```

If you were consistently using snake_case, I might defend that as a stylistic choice. But you use all of snake_case, camelCase, and PascalCase without any obvious principle. So defaulting to standard Java, which is camelCase for identifiers for variables and method names. Class names are PascalCase. Constants are SNAKE_UPPERCASE. If you don’t want to use the standard, you should come up with your own standard and explain it.

### Don’t `break`

unnecessarily

```
``````
for (int i = arr1_loop_index; i < arr1_length; i++) {
if (arr1[i] <= greater_val) {
```

```
``````
} else {
break;
}
```

This is hard to follow. It could be written more simply as

```
for (int i = aIndex; (i < a.length) && (a[i] <= b[bIndex]); i++) {
```

Now we can see that we want to keep looping as long as we are in the array and the current value in `a`

is less than the current value in `b`

.

I actually think that this is more difficult than necessary. Consider

```
for (; (aIndex < a.length) && (a[aIndex] <= b[bIndex]); aIndex++) {
```

No need for `i`

at all. We may have to adjust code later because this changes the value of `aIndex`

.

### Don’t repeat operations

```
``````
new_arr[lastIndexOfNewArr + 1] = arr1[i];
lastIndexOfNewArr++;
```

You do this multiple times. But consider

```
current++;
results[current] = a[aIndex];
```

If you update the index variable first, you don’t have to add one to it separately.

But I actually don’t think that we need results at all. Because we don’t need to merge the arrays to find the kth element of the merged results.

### Alternative

```
static int kthElementFrom(int[] a, int[] b, int k) {
int aIndex = 0;
int bIndex = 0;
while (aIndex + bIndex <= k) {
if (aIndex >= a.length) {
// not in a
return b[k - a.length];
}
if (bIndex >= b.length) {
// not in b
return a[k - b.length];
}
if (a[aIndex] <= b[bIndex]) {
aIndex++;
} else {
bIndex++;
}
}
aIndex--;
bIndex--;
if (aIndex < 0) {
return b[bIndex];
}
if (bIndex < 0) {
return a[aIndex];
}
// return the larger previous element
return (a[aIndex] > b[bIndex]) ? a[aIndex] : b[bIndex];
}
```

In words, what this does:

- Figures out that the kth element is greater than any element in
`a`

, so it returns it from`b`

. - Figures out that the kth element is greater than any element in
`b`

, so it returns it from`a`

. - Figures out that the kth element of one array is smaller than all the elements of the other array, so return it.
- Figures out that the current elements are past the kth and return the larger of the previous elements.

It would be possible to combine steps 3 and 4:

```
return ((bIndex < 0) || ((aIndex >= 0) && (a[aIndex] > b[bIndex]))) ? a[aIndex] : b[bIndex];
```

But I think it is easier to read the first way.

This is less code than yours.

It avoids creating a new array that it then throws away.

It is O(k)$\mathcal{O}(k)$ time, which will usually be smaller than O(n)$\mathcal{O}(n)$ time. Because k≤n$k\le n$.

As previously noted in a comment, we can actually do this in O(logn)$\mathcal{O}(\mathrm{log}n)$ time. Which is faster if logn<k$\mathrm{log}n<k$. And of course, we could choose the solution to use by comparing k$k$ and logn$\mathrm{log}n$ before running either solution. Similarly, we could do this in O(n−k)$\mathcal{O}(n-k)$ time by starting from the other end (largest to smallest rather than smallest to largest). Those differences won’t matter with smaller arrays but might at large scale.