Find Kth Element in the merged two sorted arrays?

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

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:

1. Figures out that the kth element is greater than any element in a, so it returns it from b.
2. Figures out that the kth element is greater than any element in b, so it returns it from a.
3. Figures out that the kth element of one array is smaller than all the elements of the other array, so return it.
4. 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 $mathcal{O}(k)$ time, which will usually be smaller than $mathcal{O}(n)$ time. Because $kle n$.

As previously noted in a comment, we can actually do this in $mathcal{O}(log n)$ time. Which is faster if $log n lt k$. And of course, we could choose the solution to use by comparing $k$ and $log n$ before running either solution. Similarly, we could do this in $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.