K-th Element of Two Sorted Arrays

Problem Statement

Problem Statement

You're given two sorted arrays 'arr1' and 'arr2' of size 'n' and 'm' respectively and an element 'k'.

Find the element that would be at the 'kth' position of the combined sorted array.

Position 'k' is given according to 1 - based indexing, but arrays 'arr1' and 'arr2' are using 0 - based indexing.

For Example :

Input: 'arr1' = [2, 3, 45], 'arr2' = [4, 6, 7, 8] and 'k' = 4
Output: 6
Explanation: The merged array will be [2, 3, 4, 6, 7, 8, 45]. The element at position '4' of this array is 6. Hence we return 6.

Detailed explanation ( Input/output format, Notes, Images )keyboard_arrow_down

Input Format :

The first line contains ‘n’ denoting the number of elements in ‘arr1’.

The second line contains ‘n’ space-separated integers denoting the elements of ‘arr1’.

The third line contains ‘m’ denoting the number of elements in ‘arr2’.

The fourth line contains ‘m’ space-separated integers denoting the elements of ‘arr2’.

The fifth line contains an integer ‘k’.

Output Format :

Return the 'kth' element of the combined sorted array.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Sample Input 1:

5
2 3 6 7 9
4
1 4 8 10
4

Sample Output 1:

4

Explanation Of Sample Input 1 :

The merged array will be: [1, 2, 3, 4, 6, 7, 8, 9, 10]

The element at position '4' is 4 so we return 4.

Sample Input 2:

5
1 2 3 5 6
5
4 7 8 9 100  
6

Sample Output 2:

6

Explanation Of Sample Input 2 :

The merged array will be: [1, 2, 3, 4, 5, 6, 7, 8, 9, 100]

The element at position '6'  is 6, so we return 6.

Constraints :

1 <= 'n' <= 5000
1 <= 'm' <= 5000
0 <= 'arr1[i]', 'arr2[i]' <= 10^9
1 <= 'k' <= 'n' + 'm'

'n' and 'm' denote the size of 'arr1' and 'arr2'.

Time limit: 1 second

Expected Time Complexity :

The expected time complexity is O(log('n') + log('m')). 

Intuition

Similar to Medain of two sorted array
Instead of dividing with /2 and maintaining 50=50 split for finding median

We maintain k elements on the left as asked
n-k on right


Just a small edge 

low = 0 , is incorrect as let m=6, n=5    k = 7
We cannot take 0 from m as n cannot give us 7 elements

low = max(0, k-n)

Similarly for high
if k = 2 , no need to pick up 6 from m for left side

Hence,
high = min(k, m);

Links

https://www.codingninjas.com/studio/problems/k-th-element-of-2-sorted-array_1164159?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTab=0

Video Links

https://www.youtube.com/watch?v=D1oDwWCq50g&ab_channel=takeUforward

Approach 1:

C++

#include <bits/stdc++.h>

int kthElement(vector<int>& nums1, vector<int>& nums2, int m, int n, int k) {
    if (m > n)
        return kthElement(nums2, nums1, n, m, k);

    int low = max(0, k-n), high = min(k, m);
    while (low <= high) {
        int mid1 = low + (high - low) / 2;
        int mid2 = k - mid1;

        int l1 = (mid1 > 0) ? nums1[mid1 - 1] : INT_MIN;
        int l2 = (mid2 > 0) ? nums2[mid2 - 1] : INT_MIN;
        int r1 = (mid1 < m) ? nums1[mid1] : INT_MAX;
        int r2 = (mid2 < n) ? nums2[mid2] : INT_MAX;

        if (l1 <= r2 && l2 <= r1) {
            return max(l1, l2);
        } else if (l1 > r2) {
            high = mid1 - 1;
        } else {
            low = mid1 + 1;
        }
    }

    return 0;
}

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems