Posts K-th element of two Arrays (geeksforgeeks - SDE Sheet)
Post
Cancel

K-th element of two Arrays (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given two sorted arrays arr1 and arr2 and an element k. The task is to find the element that would be at the kth position of the combined sorted array.

geeksforgeeks

SOLUTION

This problem is similar to:

Median of two sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {

    public long kthElement(int k, int arr1[], int arr2[]) {

        int n = arr1.length;
        int m = arr2.length;

        if(n > m)
            return kthElement(k, arr2, arr1);

        int total = n+m;

        // IMPORTANT:

        // l = Math.max(0, k - m):
        // This represents the smallest possible number of elements from arr1 that can contribute to the first k elements.
        // If m (length of arr2) is large enough that all k elements could potentially come from arr2 alone, l starts at 0.
        // Otherwise, it starts at k - m to ensure at least enough elements are considered from arr1 if not enough can be taken from arr2.

        // r = Math.min(k, n):
        // This represents the largest possible number of elements from arr1 that could be used to contribute to the first k elements.
        // We can't use more than n elements from arr1 since that exceeds the array's size, nor can we use more than k total elements,
        // as we're looking for the k-th element.

        int l = Math.max(0, k - m);
        int r = Math.min(k, n);

        while(l <= r){

            int i = (l + r)/2;
            int j = k - i;

            int l1 = Integer.MIN_VALUE, l2 = Integer.MIN_VALUE;
            int r1 = Integer.MAX_VALUE, r2 = Integer.MAX_VALUE;

            if(i-1 >= 0)
                l1 = arr1[i-1];
            if(i < n)
                r1 = arr1[i];

            if(j-1 >=0)
                l2 = arr2[j-1];

            if(j < m)
                r2 = arr2[j];

            if(l1 <= r2 && l2 <= r1){
                return (long) Math.max(l1, l2);
            }else if(l1 > r2){
                r = i - 1;
            }else
                l = i + 1;


        }

        return -1L;

    }

}

ANOTHER APPROACH (HAS HIGHER TIME COMPLEXITY)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
    public static int kthSmallest(int[] arr, int l, int r, int k)
    {

        // max heap
        PriorityQueue<Integer> pq = new PriorityQueue<>( (a,b) -> b-a );

        // loop through all the elements from l to r
        for(int i=l; i<=r; i++){

            // add to max heap
            pq.add(arr[i]);

            // if size of max heap is more than k, remove top most element
            if(pq.size() > k)
                pq.poll();

        }

        // at this point, top of the heap should have kth largest element
        return pq.peek();

    }
}
This post is licensed under CC BY 4.0 by the author.