Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Kth Element of Two Sorted Arrays

MEDIUMProblemSolveExternal Links

Description

You are given two arrays that are already sorted in non-decreasing order. One array has m elements and the other has n elements. Imagine merging these two arrays into a single sorted sequence without actually building it. Your task is to find the element that would sit at position k (1-indexed) in that merged sorted sequence.

For example, if the two arrays are [5, 10, 15] and [2, 6, 12, 20, 25], the merged sorted version would be [2, 5, 6, 10, 12, 15, 20, 25]. If k = 4, the answer is 10 because it is the 4th element in the merged order.

The challenge is to find this element efficiently — ideally without constructing the entire merged array. Since both input arrays are already sorted, we can exploit their sorted property to reach the answer much faster than a full merge.

Examples

Example 1

Input: a = [5, 10, 15], b = [2, 6, 12, 20, 25], k = 4

Output: 10

Explanation: If we merge both arrays into a single sorted sequence we get [2, 5, 6, 10, 12, 15, 20, 25]. Counting from position 1, the 4th element is 10. Notice that 10 originally came from array a.

Example 2

Input: a = [1, 3, 5, 7], b = [2, 4, 6], k = 5

Output: 5

Explanation: The merged sorted array is [1, 2, 3, 4, 5, 6, 7]. The 5th element is 5. Here the answer happens to be the middle element, which comes from array a.

Example 3

Input: a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5

Output: 6

Explanation: The merged sorted array is [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element is 6. Although 4 comes just before it, 6 edges it out at the 5th position.

Constraints

  • 1 ≤ m, n ≤ 10^4
  • 0 ≤ a[i], b[i] ≤ 10^9
  • 1 ≤ k ≤ m + n
  • Both arrays are sorted in non-decreasing order

Editorial

Brute Force

Intuition

The simplest way to find the kth element in the merged sorted order is to actually merge the two arrays into one big sorted array and then just pick the element at index k-1 (since arrays are zero-indexed).

Think of it like having two stacks of exam papers, each already sorted by score. To find the paper with the 5th highest score overall, you could lay all papers from both stacks on a single table in order and simply count to the 5th one.

Since both input arrays are already sorted, we can use the merge step from merge sort: compare the front elements of both arrays, pick the smaller one, place it next, and repeat. This produces the full merged sorted array in O(m + n) time.

Step-by-Step Explanation

Let's trace through with a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5:

Step 1: Initialize two pointers i = 0 (for array a) and j = 0 (for array b). Create an empty merged array.

Step 2: Compare a[0]=2 vs b[0]=1. Since 1 < 2, pick 1 from b. merged = [1]. Advance j to 1.

Step 3: Compare a[0]=2 vs b[1]=4. Since 2 < 4, pick 2 from a. merged = [1, 2]. Advance i to 1.

Step 4: Compare a[1]=3 vs b[1]=4. Since 3 < 4, pick 3 from a. merged = [1, 2, 3]. Advance i to 2.

Step 5: Compare a[2]=6 vs b[1]=4. Since 4 < 6, pick 4 from b. merged = [1, 2, 3, 4]. Advance j to 2.

Step 6: Compare a[2]=6 vs b[2]=8. Since 6 < 8, pick 6 from a. merged = [1, 2, 3, 4, 6]. Advance i to 3.

Step 7: We now have 5 elements in merged. The element at position k=5 (index 4) is 6.

Result: Return 6.

Merge Two Sorted Arrays — Finding the 5th Element — Watch as we merge two sorted arrays element by element, picking the smaller front element each time until we reach the kth position.

Algorithm

  1. Initialize two pointers i = 0 and j = 0 for arrays a and b respectively
  2. Create an empty merged array (or just a counter)
  3. While both pointers are within bounds:
    • Compare a[i] and b[j]
    • Pick the smaller element and add it to the merged result
    • Advance the pointer of the array from which the element was picked
  4. Append any remaining elements from whichever array is not yet exhausted
  5. Return merged[k - 1] (the kth element, converting from 1-indexed to 0-indexed)

Code

#include <vector>
using namespace std;

int findKthElement(const vector<int>& a, const vector<int>& b, int k) {
    int m = a.size(), n = b.size();
    vector<int> merged;
    int i = 0, j = 0;

    while (i < m && j < n) {
        if (a[i] <= b[j]) {
            merged.push_back(a[i]);
            i++;
        } else {
            merged.push_back(b[j]);
            j++;
        }
    }

    while (i < m) {
        merged.push_back(a[i]);
        i++;
    }

    while (j < n) {
        merged.push_back(b[j]);
        j++;
    }

    return merged[k - 1];
}
def findKthElement(a, b, k):
    m, n = len(a), len(b)
    merged = []
    i, j = 0, 0

    while i < m and j < n:
        if a[i] <= b[j]:
            merged.append(a[i])
            i += 1
        else:
            merged.append(b[j])
            j += 1

    while i < m:
        merged.append(a[i])
        i += 1

    while j < n:
        merged.append(b[j])
        j += 1

    return merged[k - 1]
import java.util.*;

class Solution {
    public int findKthElement(int[] a, int[] b, int k) {
        int m = a.length, n = b.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, d = 0;

        while (i < m && j < n) {
            if (a[i] <= b[j]) {
                merged[d++] = a[i++];
            } else {
                merged[d++] = b[j++];
            }
        }

        while (i < m) merged[d++] = a[i++];
        while (j < n) merged[d++] = b[j++];

        return merged[k - 1];
    }
}

Complexity Analysis

Time Complexity: O(m + n)

We traverse both arrays completely during the merge process. Each element from both arrays is visited exactly once, giving us m + n operations in total.

Space Complexity: O(m + n)

We create a new merged array that stores all m + n elements. This auxiliary space usage is proportional to the total number of elements across both input arrays.

Why This Approach Is Not Efficient

The brute force merges all m + n elements even though we only need the first k. If k is small (say k = 3) but the arrays together have 20,000 elements, we are doing 20,000 operations when only 3 comparisons would suffice.

Additionally, we allocate O(m + n) extra space for the merged array, which is wasteful since we only need one element from it.

Key insight: We do not need to build the entire merged array. We only need to advance through the merge process until we reach the kth element. This means we can stop after exactly k steps instead of m + n steps.

Better Approach - Merge Until K

Intuition

Instead of merging both arrays completely, we can simulate the merge but stop as soon as we have counted k elements. We do not even need to store the merged elements — we just need to keep track of the last element we picked.

Imagine two checkout lanes at a store, both serving customers in order of arrival time. You want to know who the 5th customer served overall will be. You do not need to serve everyone — you just compare the front of each lane, serve the earlier arrival, and count until you reach 5. The moment you hit 5, you have your answer.

This reduces our time from O(m + n) to O(k) and eliminates the need for extra space entirely.

Step-by-Step Explanation

Let's trace with a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5:

Step 1: Initialize i = 0, j = 0, count = 0, last = 0. We will iterate exactly k = 5 times.

Step 2: Iteration 1: Compare a[0]=2 vs b[0]=1. Pick 1 (from b). last = 1, j = 1, count = 1.

Step 3: Iteration 2: Compare a[0]=2 vs b[1]=4. Pick 2 (from a). last = 2, i = 1, count = 2.

Step 4: Iteration 3: Compare a[1]=3 vs b[1]=4. Pick 3 (from a). last = 3, i = 2, count = 3.

Step 5: Iteration 4: Compare a[2]=6 vs b[1]=4. Pick 4 (from b). last = 4, j = 2, count = 4.

Step 6: Iteration 5: Compare a[2]=6 vs b[2]=8. Pick 6 (from a). last = 6, i = 3, count = 5.

Step 7: count equals k. Return last = 6.

Optimized Merge — Stop at K — Instead of merging everything, we stop the merge process the instant we have counted k elements. The last element picked is our answer.

Algorithm

  1. Initialize two pointers i = 0, j = 0 and a variable last = 0
  2. Run a loop exactly k times:
    • If i is within bounds of a AND either j is out of bounds of b OR a[i] <= b[j]:
      • Set last = a[i] and increment i
    • Otherwise:
      • Set last = b[j] and increment j
  3. After the loop, return last — it holds the kth element

Code

#include <vector>
using namespace std;

int findKthElement(const vector<int>& a, const vector<int>& b, int k) {
    int m = a.size(), n = b.size();
    int i = 0, j = 0;
    int last = 0;

    for (int d = 0; d < k; d++) {
        if (i < m && (j >= n || a[i] <= b[j])) {
            last = a[i];
            i++;
        } else {
            last = b[j];
            j++;
        }
    }

    return last;
}
def findKthElement(a, b, k):
    m, n = len(a), len(b)
    i, j = 0, 0
    last = 0

    for _ in range(k):
        if i < m and (j >= n or a[i] <= b[j]):
            last = a[i]
            i += 1
        else:
            last = b[j]
            j += 1

    return last
class Solution {
    public int findKthElement(int[] a, int[] b, int k) {
        int m = a.length, n = b.length;
        int i = 0, j = 0;
        int last = 0;

        for (int d = 0; d < k; d++) {
            if (i < m && (j >= n || a[i] <= b[j])) {
                last = a[i];
                i++;
            } else {
                last = b[j];
                j++;
            }
        }

        return last;
    }
}

Complexity Analysis

Time Complexity: O(k)

We perform exactly k iterations of the merge loop. Each iteration does one comparison and one pointer advancement — both O(1) operations. Since k can be at most m + n, the worst case is still O(m + n), but in practice k is often much smaller.

Space Complexity: O(1)

We only use a constant number of variables (i, j, last, d). No extra array is needed since we do not store the merged elements.

Why This Approach Is Not Efficient

While O(k) is a significant improvement, it can still be slow. Consider two arrays each of size 10,000 and k = 20,000 (the last element). In this case O(k) = O(m + n), which is the same as brute force.

More importantly, we are not leveraging the sorted property to its full potential. In a sorted array, binary search can skip vast swaths of elements in O(log n) time. The linear merge inspects elements one by one, but both arrays are sorted — which means we can use a partitioning strategy to jump directly to the answer.

Key insight: Instead of counting elements one at a time, we can use binary search to partition both arrays such that exactly k elements fall on the "left" side. This gives us O(log(min(m, n))) time — exponentially faster than O(k).

Optimal Approach - Binary Search on Partition

Intuition

The idea is inspired by the binary search approach for finding the median of two sorted arrays. Instead of merging elements one by one, we decide how many elements to take from each array so that the total is exactly k.

Imagine you are organizing a relay race with exactly k runners from two teams. Team A has m runners sorted by speed, Team B has n runners also sorted by speed. You need to select exactly k runners total such that every selected runner is slower than every non-selected runner. How do you decide the split?

You can binary search on how many runners to take from Team A. If you take mid1 runners from A, you must take mid2 = k - mid1 runners from B to get exactly k total. Then you check: are all selected runners indeed slower than all non-selected ones? If the largest selected runner from A is greater than the smallest non-selected runner from B, you took too many from A (shift left). If the largest selected from B exceeds the smallest non-selected from A, you took too few from A (shift right).

The answer is the maximum of the largest elements from the left halves of both arrays — that maximum is the kth element in the merged order.

To keep the binary search efficient, we always search on the smaller array, giving us O(log(min(m, n))) time.

Step-by-Step Explanation

Let's trace with a = [2, 3, 6, 7, 9], b = [1, 4, 8, 10], k = 5:

First, ensure a is the smaller array. |a| = 5, |b| = 4. Since a is larger, swap: now a = [1, 4, 8, 10] (size 4), b = [2, 3, 6, 7, 9] (size 5).

Step 1: Set binary search bounds.

  • lo = max(0, k - n) = max(0, 5 - 5) = 0
  • hi = min(k, m) = min(5, 4) = 4
  • lo = 0, hi = 4. We search for mid1 (number of elements from a in the left partition).

Step 2: First iteration: mid1 = (0 + 4) / 2 = 2. mid2 = k - mid1 = 5 - 2 = 3.

  • From a, left partition = a[0..1] = [1, 4]. Right starts at a[2] = 8.
  • From b, left partition = b[0..2] = [2, 3, 6]. Right starts at b[3] = 7.
  • l1 = a[mid1-1] = a[1] = 4, l2 = b[mid2-1] = b[2] = 6
  • r1 = a[mid1] = a[2] = 8, r2 = b[mid2] = b[3] = 7
  • Check: l1 ≤ r2? 4 ≤ 7 ✓. Check: l2 ≤ r1? 6 ≤ 8 ✓. Both conditions met!

Step 3: Valid partition found. The kth element = max(l1, l2) = max(4, 6) = 6.

Result: Return 6.

Binary Search Partition — Finding Kth Element — Watch how binary search partitions two sorted arrays so that exactly k elements fall on the left side, finding the kth element without merging.

Algorithm

  1. If array a is larger than b, swap them so that a is always the smaller array
  2. Set lo = max(0, k - n) and hi = min(k, m) (bounds on how many elements from a go in the left partition)
  3. Binary search while lo ≤ hi:
    • Compute mid1 = (lo + hi) / 2 — number of elements from a
    • Compute mid2 = k - mid1 — number of elements from b
    • Find boundary values:
      • l1 = a[mid1 - 1] if mid1 > 0, else -∞
      • l2 = b[mid2 - 1] if mid2 > 0, else -∞
      • r1 = a[mid1] if mid1 < m, else +∞
      • r2 = b[mid2] if mid2 < n, else +∞
    • If l1 ≤ r2 AND l2 ≤ r1: valid partition → return max(l1, l2)
    • Else if l1 > r2: took too many from a → hi = mid1 - 1
    • Else: took too few from a → lo = mid1 + 1
  4. Return -1 (should not reach here if inputs are valid)

Code

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

int findKthElement(vector<int>& a, vector<int>& b, int k) {
    int m = a.size(), n = b.size();

    // Ensure a is the smaller array
    if (m > n) return findKthElement(b, a, k);

    int lo = max(0, k - n);
    int hi = min(k, m);

    while (lo <= hi) {
        int mid1 = (lo + hi) / 2;
        int mid2 = k - mid1;

        int l1 = (mid1 == 0) ? INT_MIN : a[mid1 - 1];
        int l2 = (mid2 == 0) ? INT_MIN : b[mid2 - 1];
        int r1 = (mid1 == m) ? INT_MAX : a[mid1];
        int r2 = (mid2 == n) ? INT_MAX : b[mid2];

        if (l1 <= r2 && l2 <= r1) {
            return max(l1, l2);
        } else if (l1 > r2) {
            hi = mid1 - 1;
        } else {
            lo = mid1 + 1;
        }
    }

    return -1;
}
def findKthElement(a, b, k):
    m, n = len(a), len(b)

    # Ensure a is the smaller array
    if m > n:
        return findKthElement(b, a, k)

    lo = max(0, k - n)
    hi = min(k, m)

    while lo <= hi:
        mid1 = (lo + hi) // 2
        mid2 = k - mid1

        l1 = float('-inf') if mid1 == 0 else a[mid1 - 1]
        l2 = float('-inf') if mid2 == 0 else b[mid2 - 1]
        r1 = float('inf') if mid1 == m else a[mid1]
        r2 = float('inf') if mid2 == n else b[mid2]

        if l1 <= r2 and l2 <= r1:
            return max(l1, l2)
        elif l1 > r2:
            hi = mid1 - 1
        else:
            lo = mid1 + 1

    return -1
import java.util.*;

class Solution {
    public int findKthElement(int[] a, int[] b, int k) {
        int m = a.length, n = b.length;

        // Ensure a is the smaller array
        if (m > n) return findKthElement(b, a, k);

        int lo = Math.max(0, k - n);
        int hi = Math.min(k, m);

        while (lo <= hi) {
            int mid1 = (lo + hi) / 2;
            int mid2 = k - mid1;

            int l1 = (mid1 == 0) ? Integer.MIN_VALUE : a[mid1 - 1];
            int l2 = (mid2 == 0) ? Integer.MIN_VALUE : b[mid2 - 1];
            int r1 = (mid1 == m) ? Integer.MAX_VALUE : a[mid1];
            int r2 = (mid2 == n) ? Integer.MAX_VALUE : b[mid2];

            if (l1 <= r2 && l2 <= r1) {
                return Math.max(l1, l2);
            } else if (l1 > r2) {
                hi = mid1 - 1;
            } else {
                lo = mid1 + 1;
            }
        }

        return -1;
    }
}

Complexity Analysis

Time Complexity: O(log(min(m, n)))

We perform binary search on the smaller array. In each iteration, we halve the search space. Since the search space is at most min(m, n), the number of iterations is logarithmic in the smaller array's size. Each iteration does O(1) work (computing indices and comparisons).

Space Complexity: O(1)

We only use a constant number of variables (lo, hi, mid1, mid2, l1, l2, r1, r2). No additional arrays or data structures are allocated. The recursive call to swap arrays can be converted to an iterative swap to avoid stack space, but even the recursive version uses O(1) extra space since it is a tail call.