Finding the K-th Element of Two Sorted Arrays: Deep Explanation & Solutions

Finding the k-th element of two sorted arrays is one of the most classic and frequently asked algorithmic challenges in technical interviews at top-tier software companies. While a straightforward linear solution is intuitive, developers are often expected to deliver an optimal logarithmic solution. This algorithm forms the logical backbone for solving more complex problems, such as finding the median of two sorted arrays.

In this comprehensive guide, we will break down the problem from first principles, walk through the naive approach, explain the mathematical intuition behind the optimal binary search method, and provide production-ready solutions in JavaScript, Python, Java, and C/C++.

Understanding the Problem

Let's define the problem statement clearly. Given two sorted arrays, arr1 of size m and arr2 of size n, and an integer k (where 1 <= k <= m + n), we need to find the element that would occupy the k-th position in the combined, sorted array of both inputs. The target must be achieved ideally without wasting physical memory to merge the arrays.

For example, consider the following parameters:

• arr1 = [2, 3, 6, 7, 9]

• arr2 = [1, 4, 8, 10]

• k = 5

If we were to merge these two arrays into a single sorted structure, it would look like: [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element in this combined array is 6.

Before diving into advanced algorithmic architectures, ensure you have a firm grasp of underlying data structures. You can build up your fundamentals using this beginner-friendly guide to mastering array data structure in JavaScript.

The Naive Approach: Two-Pointer Linear Scan

The most intuitive way to solve this is by using a modified two-pointer strategy inspired by the merge step of the classic Merge Sort algorithm. Instead of sorting the entire combined array, we maintain two pointers pointing to the beginning of each array. We advance the pointer pointing to the smaller element, decrementing k with each step, until we reach the k-th element.

Algorithmic Steps:

1. Initialize two pointers, p1 = 0 and p2 = 0.

2. Compare arr1[p1] and arr2[p2].

3. Advance the pointer with the smaller value and decrement k.

4. If one array is exhausted, pull remaining elements from the non-empty array.

5. Stop when k == 0 and return the last visited element.

Complexity Analysis:

• Time Complexity: O(k) — In the worst-case scenario, if k is close to m + n, the runtime scales linearly: O(m + n).

• Space Complexity: O(1) — We only store a few pointer variables, making it memory-efficient.

The Optimal Approach: Binary Search & Partitioning

To break past the linear time barrier, we must utilize the sorted property of the input arrays. We can achieve a time complexity of O(log(min(m, n))) by treating the problem as a partitioning problem and applying Binary Search.

The Logic Behind Partitioning

We want to divide both arrays into two parts—a left half and a right half—such that the left half contains exactly k elements. If we can find the exact point to split arr1 and arr2, then the maximum element in the left half of the partition is our answer.

Let us define partition variables i (number of elements taken from arr1) and j (number of elements taken from arr2). They must satisfy the following constraints:

• i + j = k (the left half has exactly k elements).

• arr1[i - 1] <= arr2[j] (all elements on the left of arr1 partition must be smaller than the right of arr2).

• arr2[j - 1] <= arr1[i] (all elements on the left of arr2 partition must be smaller than the right of arr1).

Because we know j = k - i, we only need to search for the correct index i in arr1. Since arr1 is sorted, we can use binary search to locate i within the range [max(0, k - n), min(k, m)].

Edge Case Warning: If the partition index i or j is at the extreme boundaries (0 or array length), we assign negative infinity (-∞) for left elements and positive infinity (+∞) for right elements to prevent out-of-bounds exceptions.

Multi-Language Implementations

1. JavaScript Solution

When implementing performance-critical search logic in JS, utilizing highly optimized loops and scoping variables correctly is essential. For clean, standard-compliant implementations in modern applications, keep these architectures aligned with modern JavaScript best practices in 2026.

function findKthElement(arr1, arr2, k) {
    // Ensure arr1 is the smaller array to optimize binary search range
    if (arr1.length > arr2.length) {
        return findKthElement(arr2, arr1, k);
    }

    const m = arr1.length;
    const n = arr2.length;
    let low = Math.max(0, k - n);
    let high = Math.min(k, m);

    while (low <= high) {
        const i = Math.floor((low + high) / 2);
        const j = k - i;

        const left1 = i === 0 ? -Infinity : arr1[i - 1];
        const right1 = i === m ? Infinity : arr1[i];
        const left2 = j === 0 ? -Infinity : arr2[j - 1];
        const right2 = j === n ? Infinity : arr2[j];

        if (left1 <= right2 && left2 <= right1) {
            return Math.max(left1, left2);
        } else if (left1 > right2) {
            high = i - 1; // Move left in arr1
        } else {
            low = i + 1; // Move right in arr1
        }
    }
    return -1;
}

2. Python Solution

Python offers great readability, but we must use integer division (//) to find our midpoint and represent infinity cleanly using float('-inf') and float('inf').

def find_kth_element(arr1, arr2, k):
    if len(arr1) > len(arr2):
        return find_kth_element(arr2, arr1, k)

    m, n = len(arr1), len(arr2)
    low = max(0, k - n)
    high = min(k, m)

    while low <= high:
        i = (low + high) // 2
        j = k - i

        left1 = float('-inf') if i == 0 else arr1[i - 1]
        right1 = float('inf') if i == m else arr1[i]
        left2 = float('-inf') if j == 0 else arr2[j - 1]
        right2 = float('inf') if j == n else arr2[j]

        if left1 <= right2 and left2 <= right1:
            return max(left1, left2)
        elif left1 > right2:
            high = i - 1
        else:
            low = i + 1
    return -1

3. Java Solution

In Java, we utilize Integer.MIN_VALUE and Integer.MAX_VALUE to safely handle extreme edge values without encountering numerical overflow errors.

public class Solution {
    public static int findKthElement(int[] arr1, int[] arr2, int k) {
        if (arr1.length > arr2.length) {
            return findKthElement(arr2, arr1, k);
        }

        int m = arr1.length;
        int n = arr2.length;
        int low = Math.max(0, k - n);
        int high = Math.min(k, m);

        while (low <= high) {
            int i = (low + high) / 2;
            int j = k - i;

            int left1 = (i == 0) ? Integer.MIN_VALUE : arr1[i - 1];
            int right1 = (i == m) ? Integer.MAX_VALUE : arr1[i];
            int left2 = (j == 0) ? Integer.MIN_VALUE : arr2[j - 1];
            int right2 = (j == n) ? Integer.MAX_VALUE : arr2[j];

            if (left1 <= right2 && left2 <= right1) {
                return Math.max(left1, left2);
            } else if (left1 > right2) {
                high = i - 1;
            } else {
                low = i + 1;
            }
        }
        return -1;
    }
}

4. C/C++ Solution

We leverage C++ templates or basic structural vector calls. Using INT_MIN and INT_MAX from the <climits> library is crucial for structural boundaries.

#include <vector>
#include <algorithm>
#include <climits>

int findKthElement(const std::vector<int>& arr1, const std::vector<int>& arr2, int k) {
    if (arr1.size() > arr2.size()) {
        return findKthElement(arr2, arr1, k);
    }

    int m = arr1.size();
    int n = arr2.size();
    int low = std::max(0, k - n);
    int high = std::min(k, m);

    while (low <= high) {
        int i = (low + high) / 2;
        int j = k - i;

        int left1 = (i == 0) ? INT_MIN : arr1[i - 1];
        int right1 = (i == m) ? INT_MAX : arr1[i];
        int left2 = (j == 0) ? INT_MIN : arr2[j - 1];
        int right2 = (j == n) ? INT_MAX : arr2[j];

        if (left1 <= right2 && left2 <= right1) {
            return std::max(left1, left2);
        } else if (left1 > right2) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    return -1;
}

Complexity Profile comparison

To help you weigh the design architectures of both approaches, here is a quick visual summary of performance properties:

• Two-Pointer Approach: Time Complexity O(k) | Space Complexity O(1) | Best for smaller datasets where k is small.

• Binary Search Approach: Time Complexity O(log(min(m, n))) | Space Complexity O(1) | Optimal for huge arrays or when k is close to (m + n) / 2.

Conclusion

Mastering the k-th element of two sorted arrays algorithm demonstrates a strong understanding of divide-and-conquer principles. While the linear two-pointer scanning approach is useful for short runs, binary partition search remains the gold standard for latency-critical applications. Implement the correct partition boundaries, carefully handle boundaries using type-safe minimal and maximal constants, and choose the programming language optimized to serve your platform's operational bottlenecks.