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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question