Kth Element of Two Sorted Arrays — Binary Elimination [GFG/Interview Classic]

Problem Statement#

Given two sorted arrays A and B, find the k-th smallest element in the combined sorted sequence (without merging the arrays).

Constraints:

• 1 <= len(A), len(B) <= 10^6
• Arrays are sorted in non-decreasing order
• 1 <= k <= len(A) + len(B)

Input:  A = [2, 3, 6, 7, 9], B = [1, 4, 8, 10], k = 5
Output: 6
Explanation: Merged: [1,2,3,4,6,7,8,9,10]. 5th element is 6.

Input:  A = [100, 112, 256, 349, 770], B = [72, 86, 113, 119, 265, 445, 892], k = 7
Output: 256

Why This Problem Matters#

The kth element of two sorted arrays is the direct generalisation of LC 4 (Median of Two Sorted Arrays) and is asked by Google and Amazon when they want to test advanced binary search reasoning. LC 4 is just the special case where k = (m + n) / 2.

The binary elimination technique — eliminating k//2 candidates at each step — reduces k by half each iteration, giving O(log k) time. Since k <= m + n, this is O(log(m + n)).

Understanding this problem deeply makes LC 4 (a very frequent Google hard question) straightforward to derive.

The Core Insight#

At each step, compare A[k//2 - 1] and B[k//2 - 1] (the k//2-th element of each remaining array). If A[k//2 - 1] <= B[k//2 - 1]:

• All elements in A[0 .. k//2 - 1] are smaller than B[k//2 - 1]
• At most k//2 - 1 elements from A and k//2 - 1 elements from B precede B[k//2 - 1]
• So A[k//2 - 1] cannot be the kth element — safely eliminate A[0 .. k//2 - 1]

Reduce k by the number of eliminated elements. Recurse until k == 1 (return the minimum of the two current front elements) or one array is exhausted.

Visual Dry Run#

A = [2,3,6,7,9], B = [1,4,8,10], k = 5

Round 1: k=5, half=2. A[1]=3, B[1]=4. A[1] <= B[1], eliminate A[0..1]=[2,3]. k = 5-2 = 3. Remaining: A = [6,7,9], B = [1,4,8,10]

Round 2: k=3, half=1. A[0]=6, B[0]=1. B[0] < A[0], eliminate B[0..0]=[1]. k = 3-1 = 2. Remaining: A = [6,7,9], B = [4,8,10]

Round 3: k=2, half=1. A[0]=6, B[0]=4. B[0] < A[0], eliminate B[0..0]=[4]. k = 2-1 = 1. Remaining: A = [6,7,9], B = [8,10]

Round 4: k=1. Return min(A[0], B[0]) = min(6, 8) = 6. Correct.

Solution (Optimal)#

def findKthElement(A: list[int], B: list[int], k: int) -> int:
    def helper(a, b, k):
        # Base cases
        if not a:
            return b[k - 1]
        if not b:
            return a[k - 1]
        if k == 1:
            return min(a[0], b[0])
 
        # Compare k//2-th elements (indices k//2-1)
        half = k // 2
        a_idx = min(half, len(a)) - 1
        b_idx = min(half, len(b)) - 1
 
        if a[a_idx] <= b[b_idx]:
            # Eliminate first (a_idx+1) elements from a
            return helper(a[a_idx + 1:], b, k - a_idx - 1)
        else:
            # Eliminate first (b_idx+1) elements from b
            return helper(a, b[b_idx + 1:], k - b_idx - 1)
 
    return helper(A, B, k)

function findKthElement(A, B, k) {
    function helper(a, ia, b, ib, k) {
        // Use index pointers to avoid array copying
        if (ia >= a.length) return b[ib + k - 1];
        if (ib >= b.length) return a[ia + k - 1];
        if (k === 1) return Math.min(a[ia], b[ib]);
 
        const half = Math.floor(k / 2);
        const aIdx = Math.min(half, a.length - ia) - 1;
        const bIdx = Math.min(half, b.length - ib) - 1;
 
        const aVal = a[ia + aIdx];
        const bVal = b[ib + bIdx];
 
        if (aVal <= bVal) {
            return helper(a, ia + aIdx + 1, b, ib, k - aIdx - 1);
        } else {
            return helper(a, ia, b, ib + bIdx + 1, k - bIdx - 1);
        }
    }
 
    return helper(A, 0, B, 0, k);
}

Time: O(log k) = O(log(m + n)) — k halves each step Space: O(log k) recursive call stack (O(1) with iterative version using index pointers)

Common Mistakes#

• Using k//2 as the index (off by one) — the index is k//2 - 1 (0-indexed), not k//2.
• Not capping the index at array length: when the remaining array has fewer than k//2 elements, use the last valid index.
• Forgetting to reduce k by the correct amount — reduce by a_idx + 1 (not by half), since you eliminate a_idx + 1 elements.
• Array slicing in each recursive call — creates O(k) extra space. Use index pointers instead for O(1) extra space per call.

Interview Tips#

• Before coding, state the key invariant: "we maintain that the answer is the k-th smallest in the remaining parts of A and B."
• Walk through the elimination logic slowly — explain WHY A[0..a_idx] cannot be the kth element before coding.
• The JavaScript version with index pointers avoids array copying and is production-quality.
• LC 4 (Median of Two Sorted Arrays) is solved by calling this with k = (m + n + 1) // 2 (for odd-total) or averaging two calls (for even-total).

Follow-up Questions#

• LC 4 (Median of Two Sorted Arrays): Special case where k = (m + n) / 2. Use this algorithm directly.
• Can you do it iteratively? Yes — use index pointers ia and ib instead of slicing, and replace recursion with a loop.
• What if the arrays have duplicates? The algorithm handles duplicates correctly — equal elements are fine.
• What if k is larger than both array lengths? Impossible by the constraint k <= m + n. But the base cases handle partial arrays already.

Key Takeaways#

• The kth-element-of-two-sorted-arrays algorithm uses binary elimination: at each step, safely eliminate k//2 elements from one array, reducing k by that amount.
• Compare A[min(k//2, len(A)) - 1] and B[min(k//2, len(B)) - 1]: the array with the smaller element loses k//2 elements from its front.
• The algorithm runs in O(log k) time — k halves each iteration, and k <= m + n, so the total is O(log(m + n)).
• Base cases: one array exhausted (return the other's k-th element), k = 1 (return the minimum front element).
• Use index pointers instead of array slicing to achieve O(1) extra space per call, O(log k) total stack space.
• LC 4 (Median of Two Sorted Arrays) is a direct application of this algorithm — understanding this problem makes LC 4 straightforward.
• Google and Amazon ask this to test whether candidates can derive efficient binary elimination reasoning for hard divide-and-conquer problems.