> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/k-th-element-of-two-sorted-arrays.md). # 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 ### Video Links ### Approach 1: ``` ``` {% code title="C++" lineNumbers="true" %} ```cpp #include int kthElement(vector& nums1, vector& 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; } ``` {% endcode %} ### Approach 2: ``` ``` {% code title="C++" lineNumbers="true" %} ```cpp ``` {% endcode %} ### Approach 3: ``` ``` {% code title="C++" lineNumbers="true" %} ```cpp ``` {% endcode %} ### Approach 4: ``` ``` {% code title="C++" lineNumbers="true" %} ```cpp ``` {% endcode %} ### Similar Problems ###