# K-th Element of Two Sorted Arrays

## Problem Statement

<br>

### Problem Statement

**You're given two sorted arrays&#x20;*****'arr1'*****&#x20;and&#x20;*****'arr2'*****&#x20;of size&#x20;*****'n'*****&#x20;and&#x20;*****'m'*****&#x20;respectively and an element&#x20;*****'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.
```

<br>

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:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
#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;
}

```

{% 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/k-th-element-of-two-sorted-arrays.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.