K-th Element of Two Sorted Arrays

Given two sorted arrays arr1 and arr2, and a number k, your task is to find the K-th smallest element in the merged array formed by combining both arrays.

• Both arrays are individually sorted in non-decreasing order.
• You are not allowed to fully merge the arrays or use extra space.
• Find the result using an efficient approach.

If either array is empty, the answer will depend entirely on the other array. If k is invalid (e.g., larger than total elements), return -1.

Understanding the Problem

We are given two sorted arrays and a number k. Our goal is to find the k-th smallest element in the combined sorted form of these two arrays. But we are not supposed to merge them completely.

For a beginner, imagine placing all elements from both arrays into one big array and sorting it. Then, the k-th element is simply at index k - 1. But this is inefficient. So instead, we use a smart trick called binary search to figure out the answer without merging.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s take arr1 = [2, 3, 6, 7, 9] and arr2 = [1, 4, 8, 10], and we want to find k = 5.

If we merge and sort: [1, 2, 3, 4, 6, 7, 8, 9, 10], the 5th smallest element is 6. We’ll now try to find 6 without merging.

Step 2: Always Binary Search the Smaller Array

We always do binary search on the smaller array to keep the process efficient. In our case, arr2 is smaller (4 elements), so we search there.

Step 3: Understand the Partition Logic

We divide arr2 such that we take cut2 elements from it and cut1 = k - cut2 from arr1.

We want all elements on the left side (from both arrays) to be less than or equal to the elements on the right side. We compare the largest on the left and the smallest on the right to check this.

Step 4: Perform Binary Search

We initialize low = max(0, k - len(arr1)) and high = min(k, len(arr2)).

We perform binary search between low and high, computing cut2 in the middle, and getting cut1 = k - cut2.

We extract four values:

• l1 = -Infinity if cut1 == 0 else arr1[cut1 - 1]
• l2 = -Infinity if cut2 == 0 else arr2[cut2 - 1]
• r1 = Infinity if cut1 == len(arr1) else arr1[cut1]
• r2 = Infinity if cut2 == len(arr2) else arr2[cut2]

We check if l1 ≤ r2 and l2 ≤ r1. If true, the answer is max(l1, l2).

If l1 > r2, move left: high = cut2 - 1. If l2 > r1, move right: low = cut2 + 1.

Step 5: Return the Final Answer

When the correct partition is found, return max(l1, l2) as the k-th smallest element.

Edge Cases

Empty Array

If one array is empty, just return the k-th element from the other array directly.

Example: arr1 = [], arr2 = [5, 7, 9], k = 2 → Answer is 7.

K is Out of Range

If k > len(arr1) + len(arr2), it's invalid. We return -1 or a suitable error message.

All Elements are Same

Even if all elements are the same, the logic still works. The partitions will respect the counts, not the values.

Highly Unbalanced Lengths

Even if one array is very short and the other is long, binary search will happen on the smaller one, so performance remains efficient.

Finally

This approach avoids merging the arrays completely and instead finds the correct "cut" using binary search. This gives us a time complexity of O(log(min(n, m))), which is much faster than the naive approach.

By handling edge cases smartly and applying partitioning logic carefully, we can find the k-th smallest element in two sorted arrays in a time-efficient and space-efficient manner, perfect for both interviews and real-world problems.

1. Let arr1 be the smaller array among the two. If not, swap arr1 and arr2.
2. Let n = arr1.length and m = arr2.length.
3. Set low = max(0, k - m) and high = min(k, n).
4. While low ≤ high, do:
5. → Set cut1 = (low + high) / 2, cut2 = k - cut1.
6. → Use l1 = -∞ if cut1 == 0, else arr1[cut1 - 1].
7. → Use l2 = -∞ if cut2 == 0, else arr2[cut2 - 1].
8. → Use r1 = ∞ if cut1 == n, else arr1[cut1].
9. → Use r2 = ∞ if cut2 == m, else arr2[cut2].
10. If l1 ≤ r2 and l2 ≤ r1, return max(l1, l2).
11. Else if l1 > r2, move left: high = cut1 - 1.
12. Else, move right: low = cut1 + 1.

#include <stdio.h>
#include <limits.h>

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int findKthElement(int* A, int* B, int n, int m, int k) {
    if (n > m) return findKthElement(B, A, m, n, k);
    int low = max(0, k - m), high = min(k, n);

    while (low <= high) {
        int cut1 = (low + high) / 2;
        int cut2 = k - cut1;

        int l1 = cut1 == 0 ? INT_MIN : A[cut1 - 1];
        int l2 = cut2 == 0 ? INT_MIN : B[cut2 - 1];
        int r1 = cut1 == n ? INT_MAX : A[cut1];
        int r2 = cut2 == m ? INT_MAX : B[cut2];

        if (l1 <= r2 && l2 <= r1) return max(l1, l2);
        else if (l1 > r2) high = cut1 - 1;
        else low = cut1 + 1;
    }
    return -1;
}

int main() {
    int arr1[] = {2, 3, 6, 7, 9};
    int arr2[] = {1, 4, 8, 10};
    int k = 5;
    printf("K-th element: %d\n", findKthElement(arr1, arr2, 5, 4, k));
    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int findKthElement(vector<int>& A, vector<int>& B, int k) {
    int n = A.size(), m = B.size();
    if (n > m) return findKthElement(B, A, k);

    int low = max(0, k - m), high = min(k, n);
    while (low <= high) {
        int cut1 = (low + high) / 2;
        int cut2 = k - cut1;

        int l1 = (cut1 == 0) ? INT_MIN : A[cut1 - 1];
        int l2 = (cut2 == 0) ? INT_MIN : B[cut2 - 1];
        int r1 = (cut1 == n) ? INT_MAX : A[cut1];
        int r2 = (cut2 == m) ? INT_MAX : B[cut2];

        if (l1 <= r2 && l2 <= r1) return max(l1, l2);
        else if (l1 > r2) high = cut1 - 1;
        else low = cut1 + 1;
    }
    return -1;
}

int main() {
    vector<int> arr1 = {2, 3, 6, 7, 9};
    vector<int> arr2 = {1, 4, 8, 10};
    int k = 5;
    cout << "K-th element: " << findKthElement(arr1, arr2, k) << endl;
    return 0;
}

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

    low, high = max(0, k - m), min(k, n)
    while low <= high:
        cut1 = (low + high) // 2
        cut2 = k - cut1

        l1 = float('-inf') if cut1 == 0 else arr1[cut1 - 1]
        l2 = float('-inf') if cut2 == 0 else arr2[cut2 - 1]
        r1 = float('inf') if cut1 == n else arr1[cut1]
        r2 = float('inf') if cut2 == m else arr2[cut2]

        if l1 <= r2 and l2 <= r1:
            return max(l1, l2)
        elif l1 > r2:
            high = cut1 - 1
        else:
            low = cut1 + 1
    return -1

arr1 = [2, 3, 6, 7, 9]
arr2 = [1, 4, 8, 10]
k = 5
print("K-th element:", find_kth_element(arr1, arr2, k))

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

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

    while (low <= high) {
      int cut1 = (low + high) / 2;
      int cut2 = k - cut1;

      int l1 = (cut1 == 0) ? Integer.MIN_VALUE : arr1[cut1 - 1];
      int l2 = (cut2 == 0) ? Integer.MIN_VALUE : arr2[cut2 - 1];
      int r1 = (cut1 == n) ? Integer.MAX_VALUE : arr1[cut1];
      int r2 = (cut2 == m) ? Integer.MAX_VALUE : arr2[cut2];

      if (l1 <= r2 && l2 <= r1) return Math.max(l1, l2);
      else if (l1 > r2) high = cut1 - 1;
      else low = cut1 + 1;
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr1 = {2, 3, 6, 7, 9};
    int[] arr2 = {1, 4, 8, 10};
    int k = 5;
    System.out.println("K-th element: " + findKthElement(arr1, arr2, k));
  }
}

function findKthElement(arr1, arr2, k) {
  if (arr1.length > arr2.length) return findKthElement(arr2, arr1, k);
  let n = arr1.length, m = arr2.length;
  let low = Math.max(0, k - m), high = Math.min(k, n);

  while (low <= high) {
    let cut1 = Math.floor((low + high) / 2);
    let cut2 = k - cut1;

    let l1 = cut1 === 0 ? -Infinity : arr1[cut1 - 1];
    let l2 = cut2 === 0 ? -Infinity : arr2[cut2 - 1];
    let r1 = cut1 === n ? Infinity : arr1[cut1];
    let r2 = cut2 === m ? Infinity : arr2[cut2];

    if (l1 <= r2 && l2 <= r1) return Math.max(l1, l2);
    else if (l1 > r2) high = cut1 - 1;
    else low = cut1 + 1;
  }
  return -1;
}

const arr1 = [2, 3, 6, 7, 9];
const arr2 = [1, 4, 8, 10];
const k = 5;
console.log("K-th element:", findKthElement(arr1, arr2, k));

package main

import (
  "fmt"
  "math"
)

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

func findKthElement(A, B []int, k int) int {
  if len(A) > len(B) {
    return findKthElement(B, A, k)
  }

  n, m := len(A), len(B)
  low, high := max(0, k-m), min(k, n)

  for low <= high {
    cut1 := (low + high) / 2
    cut2 := k - cut1

    l1 := math.MinInt
    if cut1 != 0 {
      l1 = A[cut1-1]
    }
    l2 := math.MinInt
    if cut2 != 0 {
      l2 = B[cut2-1]
    }
    r1 := math.MaxInt
    if cut1 != n {
      r1 = A[cut1]
    }
    r2 := math.MaxInt
    if cut2 != m {
      r2 = B[cut2]
    }

    if l1 <= r2 && l2 <= r1 {
      return max(l1, l2)
    } else if l1 > r2 {
      high = cut1 - 1
    } else {
      low = cut1 + 1
    }
  }
  return -1
}

func main() {
  arr1 := []int{2, 3, 6, 7, 9}
  arr2 := []int{1, 4, 8, 10}
  k := 5
  fmt.Println("K-th element:", findKthElement(arr1, arr2, k))
}

fn find_kth_element(a: &[i32], b: &[i32], k: usize) -> i32 {
    let (a, b) = if a.len() > b.len() { (b, a) } else { (a, b) };
    let (n, m) = (a.len(), b.len());
    let (mut low, mut high) = (k.saturating_sub(m), std::cmp::min(k, n));

    while low <= high {
        let cut1 = (low + high) / 2;
        let cut2 = k - cut1;

        let l1 = if cut1 == 0 { i32::MIN } else { a[cut1 - 1] };
        let l2 = if cut2 == 0 { i32::MIN } else { b[cut2 - 1] };
        let r1 = if cut1 == n { i32::MAX } else { a[cut1] };
        let r2 = if cut2 == m { i32::MAX } else { b[cut2] };

        if l1 <= r2 && l2 <= r1 {
            return l1.max(l2);
        } else if l1 > r2 {
            high = cut1 - 1;
        } else {
            low = cut1 + 1;
        }
    }
    -1
}

fn main() {
    let arr1 = vec![2, 3, 6, 7, 9];
    let arr2 = vec![1, 4, 8, 10];
    let k = 5;
    println!("K-th element: {}", find_kth_element(&arr1, &arr2, k));
}

fun findKthElement(arr1: IntArray, arr2: IntArray, k: Int): Int {
    if (arr1.size > arr2.size) return findKthElement(arr2, arr1, k)
    var low = maxOf(0, k - arr2.size)
    var high = minOf(k, arr1.size)
    while (low <= high) {
        val cut1 = (low + high) / 2
        val cut2 = k - cut1
        val l1 = if (cut1 == 0) Int.MIN_VALUE else arr1[cut1 - 1]
        val l2 = if (cut2 == 0) Int.MIN_VALUE else arr2[cut2 - 1]
        val r1 = if (cut1 == arr1.size) Int.MAX_VALUE else arr1[cut1]
        val r2 = if (cut2 == arr2.size) Int.MAX_VALUE else arr2[cut2]

        if (l1 <= r2 && l2 <= r1) return maxOf(l1, l2)
        else if (l1 > r2) high = cut1 - 1
        else low = cut1 + 1
    }
    return -1
}

fun main() {
    val arr1 = intArrayOf(2, 3, 6, 7, 9)
    val arr2 = intArrayOf(1, 4, 8, 10)
    val k = 5
    println("K-th element: ${findKthElement(arr1, arr2, k)}")
}

func findKthElement(_ arr1: [Int], _ arr2: [Int], _ k: Int) -> Int {
    var A = arr1, B = arr2
    if A.count > B.count {
        swap(&A, &B)
    }
    let n = A.count, m = B.count
    var low = max(0, k - m), high = min(k, n)

    while low <= high {
        let cut1 = (low + high) / 2
        let cut2 = k - cut1

        let l1 = (cut1 == 0) ? Int.min : A[cut1 - 1]
        let l2 = (cut2 == 0) ? Int.min : B[cut2 - 1]
        let r1 = (cut1 == n) ? Int.max : A[cut1]
        let r2 = (cut2 == m) ? Int.max : B[cut2]

        if l1 <= r2 && l2 <= r1 {
            return max(l1, l2)
        } else if l1 > r2 {
            high = cut1 - 1
        } else {
            low = cut1 + 1
        }
    }
    return -1
}

let arr1 = [2, 3, 6, 7, 9]
let arr2 = [1, 4, 8, 10]
let k = 5
print("K-th element: \(findKthElement(arr1, arr2, k))")

function findKthElement(arr1: number[], arr2: number[], k: number): number {
  if (arr1.length > arr2.length) return findKthElement(arr2, arr1, k);
  let n = arr1.length, m = arr2.length;
  let low = Math.max(0, k - m), high = Math.min(k, n);

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

    const l1 = cut1 === 0 ? -Infinity : arr1[cut1 - 1];
    const l2 = cut2 === 0 ? -Infinity : arr2[cut2 - 1];
    const r1 = cut1 === n ? Infinity : arr1[cut1];
    const r2 = cut2 === m ? Infinity : arr2[cut2];

    if (l1 <= r2 && l2 <= r1) return Math.max(l1, l2);
    else if (l1 > r2) high = cut1 - 1;
    else low = cut1 + 1;
  }
  return -1;
}

const arr1: number[] = [2, 3, 6, 7, 9];
const arr2: number[] = [1, 4, 8, 10];
const k = 5;
console.log("K-th element:", findKthElement(arr1, arr2, k));

Time complexity

Space complexity

O(1)

Only a constant amount of additional variables are used for computation and control.