Log inSign up
hardgfgNot Started

Kth Element of Two Sorted Arrays

Given two sorted arrays arr1 and arr2 of size n and m respectively and an element k. The task is to find the element that would be at the kth position of the final sorted array.

Binary Search
Solve on gfg
Lesson

Problem Statement

Given two sorted arrays arr1 and arr2 of size n and m respectively and an element k. The task is to find the element that would be at the k-th position of the combined sorted array in O(log(min(n, m))) time.

Example 1 · Example 1: Standard Search:

Input: arr1 = [2, 3, 6, 7, 9], arr2 = [1, 4, 8, 10], k = 5
Output: 6
Explanation: Merged sorted array: [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element is 6.

Example 2 · Example 2: All from Second Array:

Input: arr1 = [100, 112, 256, 349, 770], arr2 = [72, 86, 113, 119, 265, 445, 892], k = 7
Output: 256
Explanation: The 7th element in sorted combined order is 256.

Constraints:

  • 1 <= arr1.length, arr2.length <= 106
  • 0 <= arr1[i], arr2[i] <= 109
  • 1 <= k <= arr1.length + arr2.length

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the dual-array partition cut technique.
  • Derive precise bounds [max(0, k - m), min(k, n)] for the cut index.
  • Handle boundary infinities cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find k-th element in two sorted arrays without merging in O(m+n).
  • Strict logarithmic time requirement: O(log(min(n, m))).
  • Array partition cut technique.

Algorithmic Decision Tree:

  • Ensure n <= m by swapping if needed.
  • low = max(0, k - m), high = min(k, n).
  • cut1 = (low + high) / 2, cut2 = k - cut1.
  • If l1 <= r2 and l2 <= r1 -> return max(l1, l2).
  • If l1 > r2 -> high = cut1 - 1.
  • Else -> low = cut1 + 1.

Connected Patterns:

Median of Two Sorted ArraysBinary SearchMerge Two Sorted Arrays

1. Two-Pointer Merge

Intuition

Advance two pointers i and j. Increment a counter until the kth element is reached.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: i = 0, j = 0, count = 0, ans = -1.
  2. Step 2: While i < n and j < m: pick smaller, count++. If count == k, return element.
  3. Step 3: Exhaust remaining elements in arr1 or arr2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int kthElement(vector<int>& arr1, vector<int>& arr2, int k) {
8 int n = arr1.size(), m = arr2.size();
9 int i = 0, j = 0, count = 0, ans = -1;
10 while (i < n && j < m) {
11 if (arr1[i] <= arr2[j]) {
12 ans = arr1[i++];
13 } else {
14 ans = arr2[j++];
15 }
16 count++;
17 if (count == k) return ans;
18 }
19 while (i < n) {
20 ans = arr1[i++];
21 count++;
22 if (count == k) return ans;
23 }
24 while (j < m) {
25 ans = arr2[j++];
26 count++;
27 if (count == k) return ans;
28 }
29 return ans;
30}
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(k) — Takes k pointer increments.
  • Space complexity: O(1) — O(1) extra space.

2. Recursive Divide and Conquer (K/2 Halving)

Intuition

Recursively eliminate k/2 elements from either arr1 or arr2 by comparing their (k/2)-th elements.

When to apply: Alternative logarithmic recursive approach.

Algorithm

  1. Step 1: Base cases: if arr1 is empty return arr2[k-1]; if k == 1 return min(arr1[0], arr2[0]).
  2. Step 2: Let idx1 = min(n, k/2) - 1, idx2 = min(m, k/2) - 1.
  3. Step 3: If arr1[idx1] <= arr2[idx2], discard first idx1 + 1 elements of arr1, search k - (idx1 + 1).
  4. Step 4: Else discard first idx2 + 1 elements of arr2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int kth(int* a, int n, int* b, int m, int k) {
8 if (n > m) return kth(b, m, a, n, k);
9 if (n == 0) return b[k - 1];
10 if (k == 1) return min(a[0], b[0]);
11 int i = min(n, k / 2), j = min(m, k / 2);
12 if (a[i - 1] > b[j - 1]) return kth(a, n, b + j, m - j, k - j);
13 else return kth(a + i, n - i, b, m, k - i);
14}
15
16int main() {
17 // Sample driver execution
18 cout << "Execution completed successfully." << endl;
19 return 0;
20}
21

Time & Space Complexity

  • Time complexity: O(log k) — Recursion depth is log2(k).
  • Space complexity: O(log k) — Stack space O(log k).

3. Binary Search on Partition Cut

Intuition

Ensure arr1 is the smaller array (swap if needed). Set low = max(0, k - m), high = min(k, n). Calculate cut1 = (low + high) / 2 and cut2 = k - cut1. Compute l1, l2, r1, r2. If l1 <= r2 and l2 <= r1, return max(l1, l2). If l1 > r2, high = cut1 - 1; else low = cut1 + 1.

When to apply: Standard optimal interview solution.

Algorithm

  1. Step 1: If arr1.length > arr2.length, swap arrays.
  2. Step 2: low = max(0, k - m), high = min(k, n).
  3. Step 3: While low <= high:
  4. - cut1 = (low + high) / 2, cut2 = k - cut1.
  5. - l1 = (cut1 == 0) ? -INF : arr1[cut1 - 1].
  6. - l2 = (cut2 == 0) ? -INF : arr2[cut2 - 1].
  7. - r1 = (cut1 == n) ? +INF : arr1[cut1].
  8. - r2 = (cut2 == m) ? +INF : arr2[cut2].
  9. - If l1 <= r2 && l2 <= r1: return max(l1, l2).
  10. - If l1 > r2: high = cut1 - 1.
  11. - Else: low = cut1 + 1.

Trace for arr1 = [2, 3, 6, 7, 9], arr2 = [1, 4, 8, 10], k = 5

2 of 2 questions left today
Step 1 / 1
Trace timeline100% explored
Current operationSTEP 1 OF 1
cut1 = 3 (taking 3 elements from arr1: [2, 3, 6]), cut2 = 5 - 3 = 2 (taking 2 elements from arr2: [1, 4])
Visual state
Values and pointers at this exact step
pointers
S
[2, 3, 6]
[7, 9]
[1, 4]
[8, 10]
0
↑ cut1
1
2
↑ cut2
3
Check / comparison
l1(6) <= r2(8) && l2(4) <= r1(7) -> Valid partition found!
Decision / next transition
Return max(l1, l2) = 6.
Why this step matters

cut1 = 3 (taking 3 elements from arr1: [2, 3, 6]), cut2 = 5 - 3 = 2 (taking 2 elements from arr2: [1, 4]). l1 = 6, r1 = 7. l2 = 4, r2 = 8. Check: l1 <= r2 (6 <= 8) TRUE, l2 <= r1 (4 <= 7) TRUE. Valid partition! k-th element is max(l1, l2) = max(6, 4) = 6.

Step 1 / 1
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int kthElement(vector<int>& arr1, vector<int>& arr2, int k) {
8 int n = arr1.size(), m = arr2.size();
9 if (n > m) return kthElement(arr2, arr1, k);
10 int low = max(0, k - m), high = min(k, n);
11 while (low <= high) {
12 int cut1 = (low + high) / 2;
13 int cut2 = k - cut1;
14 int l1 = (cut1 == 0) ? INT_MIN : arr1[cut1 - 1];
15 int l2 = (cut2 == 0) ? INT_MIN : arr2[cut2 - 1];
16 int r1 = (cut1 == n) ? INT_MAX : arr1[cut1];
17 int r2 = (cut2 == m) ? INT_MAX : arr2[cut2];
18 if (l1 <= r2 && l2 <= r1) {
19 return max(l1, l2);
20 } else if (l1 > r2) {
21 high = cut1 - 1;
22 } else {
23 low = cut1 + 1;
24 }
25 }
26 return 1;
27}
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(log(min(n, m))) — Binary search on smaller array of size at most n takes log2(n) iterations.
  • Space complexity: O(1) — O(1) memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Two-Pointer MergeO(k)O(1)Advance two pointers until reaching k elements.Inspects each element up to k.
2.Divide & Conquer (K/2)O(log k)O(log k)Recursively drop k/2 elements.Recursive call overhead.
3.Binary Search on Partition CutOptimalO(log(min(n, m)))O(1)Partition smaller array using binary search.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • k = 1 -> return min(arr1[0], arr2[0]).
  • k = n + m -> return max(arr1[n-1], arr2[m-1]).
  • One array is completely exhausted before k elements.
  • Arrays contain duplicates.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why cut1 bounds are [max(0, k - m), min(k, n)] (cannot take more than n from arr1, and must take at least k - m if arr2 cannot supply all k elements).
  2. Explain the four boundary values: l1, l2, r1, r2 and use INT_MIN/INT_MAX for out of bounds.
  3. Highlight the O(log(min(n, m))) complexity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the lower bound of cut1 set to max(0, k - m)?

Back to DSA Sheet