Problem

Given two sorted arrays, find the element which would be the k-th smallest in their merged and sorted combination.

Examples

Example 1

1
2
3

Input: A = [1, 1, 2, 3, 10, 15], B = [-1, 2, 3, 4, 6, 7], k = 8
Output: 4
Explanation: The merged array is [-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15]. The 8th smallest element is 4.

Example 2

1
2
3

Input: A = [2, 5, 8], B = [1, 3, 7, 9], k = 5
Output: 5
Explanation: The merged array is [1, 2, 3, 5, 7, 8, 9]. The 5th smallest element is 7.

Constraints

  • 1 <= len(A), len(B) <= 10^5
  • -10^9 <= A[i], B[i] <= 10^9
  • 1 <= k <= len(A) + len(B)

Solution

Method 1 – Merge Approach

Intuition

By merging both sorted arrays as in merge sort, we can track the k-th smallest element directly. This is simple but not optimal for large k.

Approach

  1. Use two pointers to traverse both arrays.
  2. At each step, pick the smaller element and move the corresponding pointer.
  3. Repeat until k elements have been picked.
  4. The last picked element is the k-th smallest.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int findKthSmallest(vector<int>& a, vector<int>& b, int k) {
        int i = 0, j = 0, ans = 0;
        while (k--) {
            if (i < a.size() && (j >= b.size() || a[i] < b[j])) ans = a[i++];
            else ans = b[j++];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findKthSmallest(a, b []int, k int) int {
    i, j := 0, 0
    var ans int
    for k > 0 {
        if i < len(a) && (j >= len(b) || a[i] < b[j]) {
            ans = a[i]
            i++
        } else {
            ans = b[j]
            j++
        }
        k--
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int findKthSmallest(int[] a, int[] b, int k) {
        int i = 0, j = 0, ans = 0;
        while (k-- > 0) {
            if (i < a.length && (j >= b.length || a[i] < b[j])) ans = a[i++];
            else ans = b[j++];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findKthSmallest(a: IntArray, b: IntArray, k: Int): Int {
        var i = 0; var j = 0; var ans = 0
        var kk = k
        while (kk > 0) {
            if (i < a.size && (j >= b.size || a[i] < b[j])) { ans = a[i]; i++ }
            else { ans = b[j]; j++ }
            kk--
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find_kth_smallest(a: list[int], b: list[int], k: int) -> int:
    i, j, ans = 0, 0, 0
    while k > 0:
        if i < len(a) and (j >= len(b) or a[i] < b[j]):
            ans = a[i]
            i += 1
        else:
            ans = b[j]
            j += 1
        k -= 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn find_kth_smallest(a: Vec<i32>, b: Vec<i32>, k: i32) -> i32 {
        let (mut i, mut j, mut ans) = (0, 0, 0);
        let mut kk = k;
        while kk > 0 {
            if i < a.len() && (j >= b.len() || a[i] < b[j]) {
                ans = a[i]; i += 1;
            } else {
                ans = b[j]; j += 1;
            }
            kk -= 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    findKthSmallest(a: number[], b: number[], k: number): number {
        let i = 0, j = 0, ans = 0;
        while (k-- > 0) {
            if (i < a.length && (j >= b.length || a[i] < b[j])) ans = a[i++];
            else ans = b[j++];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k), as we perform k steps to find the k-th smallest.
  • 🧺 Space complexity: O(1), only pointers and a variable for the answer are used.

Method 2 – Binary Search Partition

Intuition

Since both arrays are sorted, we can use binary search to partition them and discard large sections, finding the k-th smallest in logarithmic time.

Approach

  1. Always binary search on the smaller array for efficiency.
  2. Let i be the number of elements taken from A, and j = k - i from B.
  3. Use binary search to find i such that:
    • A[i-1] <= B[j] and B[j-1] <= A[i]
  4. The k-th smallest is max(A[i-1], B[j-1]).
  5. Handle edge cases when i or j is 0 or at the end of the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int findKthSmallest(vector<int>& a, vector<int>& b, int k) {
        int n = a.size(), m = b.size();
        if (n > m) return findKthSmallest(b, a, k);
        int l = max(0, k - m), r = min(k, n);
        while (l < r) {
            int i = l + (r - l) / 2;
            int j = k - i;
            if (i < n && j > 0 && b[j-1] > a[i]) l = i + 1;
            else r = i;
        }
        int i = l, j = k - l;
        int aLeft = (i == 0) ? INT_MIN : a[i-1];
        int bLeft = (j == 0) ? INT_MIN : b[j-1];
        return max(aLeft, bLeft);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func findKthSmallest(a, b []int, k int) int {
    if len(a) > len(b) {
        return findKthSmallest(b, a, k)
    }
    l, r := max(0, k-len(b)), min(k, len(a))
    for l < r {
        i := l + (r-l)/2
        j := k - i
        if i < len(a) && j > 0 && b[j-1] > a[i] {
            l = i + 1
        } else {
            r = i
        }
    }
    i, j := l, k-l
    aLeft := math.MinInt32
    bLeft := math.MinInt32
    if i > 0 {
        aLeft = a[i-1]
    }
    if j > 0 {
        bLeft = b[j-1]
    }
    return max(aLeft, bLeft)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int findKthSmallest(int[] a, int[] b, int k) {
        int n = a.length, m = b.length;
        if (n > m) return findKthSmallest(b, a, k);
        int l = Math.max(0, k - m), r = Math.min(k, n);
        while (l < r) {
            int i = l + (r - l) / 2;
            int j = k - i;
            if (i < n && j > 0 && b[j-1] > a[i]) l = i + 1;
            else r = i;
        }
        int i = l, j = k - l;
        int aLeft = (i == 0) ? Integer.MIN_VALUE : a[i-1];
        int bLeft = (j == 0) ? Integer.MIN_VALUE : b[j-1];
        return Math.max(aLeft, bLeft);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun findKthSmallest(a: IntArray, b: IntArray, k: Int): Int {
        val n = a.size; val m = b.size
        if (n > m) return findKthSmallest(b, a, k)
        var l = maxOf(0, k - m); var r = minOf(k, n)
        while (l < r) {
            val i = l + (r - l) / 2
            val j = k - i
            if (i < n && j > 0 && b[j-1] > a[i]) l = i + 1
            else r = i
        }
        val i = l; val j = k - l
        val aLeft = if (i == 0) Int.MIN_VALUE else a[i-1]
        val bLeft = if (j == 0) Int.MIN_VALUE else b[j-1]
        return maxOf(aLeft, bLeft)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def find_kth_smallest(a: list[int], b: list[int], k: int) -> int:
    if len(a) > len(b):
        return find_kth_smallest(b, a, k)
    l, r = max(0, k - len(b)), min(k, len(a))
    while l < r:
        i = l + (r - l) // 2
        j = k - i
        if i < len(a) and j > 0 and b[j-1] > a[i]:
            l = i + 1
        else:
            r = i
    i, j = l, k - l
    a_left = a[i-1] if i > 0 else float('-inf')
    b_left = b[j-1] if j > 0 else float('-inf')
    return max(a_left, b_left)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_kth_smallest(a: Vec<i32>, b: Vec<i32>, k: i32) -> i32 {
        let n = a.len(); let m = b.len();
        if n > m { return Solution::find_kth_smallest(b, a, k); }
        let (mut l, mut r) = (std::cmp::max(0, k as usize - m), std::cmp::min(k as usize, n));
        while l < r {
            let i = l + (r - l) / 2;
            let j = k as usize - i;
            if i < n && j > 0 && b[j-1] > a[i] { l = i + 1; }
            else { r = i; }
        }
        let i = l; let j = k as usize - l;
        let a_left = if i == 0 { i32::MIN } else { a[i-1] };
        let b_left = if j == 0 { i32::MIN } else { b[j-1] };
        std::cmp::max(a_left, b_left)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findKthSmallest(a: number[], b: number[], k: number): number {
        if (a.length > b.length) return this.findKthSmallest(b, a, k);
        let l = Math.max(0, k - b.length), r = Math.min(k, a.length);
        while (l < r) {
            let i = l + Math.floor((r - l) / 2);
            let j = k - i;
            if (i < a.length && j > 0 && b[j-1] > a[i]) l = i + 1;
            else r = i;
        }
        let i = l, j = k - l;
        let aLeft = i === 0 ? Number.MIN_SAFE_INTEGER : a[i-1];
        let bLeft = j === 0 ? Number.MIN_SAFE_INTEGER : b[j-1];
        return Math.max(aLeft, bLeft);
    }
}

Complexity

  • ⏰ Time complexity: O(log(min(n, m))), as binary search is performed on the smaller array.
  • 🧺 Space complexity: O(1), only a few variables are used.