Kth element of 2 sorted arrays
The problem
Given two sorted arrays a and b of size m and n respectively. Find the kth element of the final sorted array.
Input: a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5 Output: 6 Explanation: The final sorted array would be [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element of this array is 6.
Input: a = [100, 112, 256, 349, 770], b = [72, 86, 113, 119, 265, 445, 892], k = 7 Output: 256 Explanation: Final sorted array is - [72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892], 7th element of this array is 256.
Input: a = [2, 3, 6], b = [7, 9], k = 4
- 1 <= m, n <= 104
- 0 <= arr1[i[, arr2[i] < 109
- 1 <= k <= m+n
cpp
class Solution {
public:
int kthElement(vector<int> &a, vector<int>& b, int k) {
}
};java
class Solution {
public int kthElement(int[] a, int[] b, int k) {
}
}python
class Solution:
def kthElement(self, a, b, k):javascript
class Solution {
kthElement(a, b, k) {
}
}csharp
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int KthElement(List<int> a, List<int> b, int k) {
}
}go
func kthElement(a []int, b []int, k int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Binary-search the smaller array's cut.
- 02Derive the other cut from k.
- 03Check the four partition boundary values.
- 04Move the cut until left values are valid.
- 05Return the larger left boundary.
Reference answer
Then expect these follow-ups
How does this lead to median of two arrays?
Tests: generalization
What if one array is empty?
Tests: boundaries
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question