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.
SOLUTION
This problem is similar to:
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();
}
}