Find K-th Element of Two Sorted Arrays - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Array 1 Array 2 k Output Description
[2, 3, 6, 7, 9] [1, 4, 8, 10] 5 4 Combined sorted array: [1,2,3,4,6,...], 5th element is 4
[1, 2, 3] [4, 5, 6] 4 4 Combined: [1,2,3,4,5,6], 4th element is 4
[1, 2] [3, 4, 5, 6] 6 6 6th smallest element overall
[1, 2, 3, 4] [] 2 2 Only one array present, pick 2nd element
[] [5, 10, 15] 3 15 Only one array present, pick 3rd element
[] [5, 10, 15] 4 -1 k = 4 is out of range (array size = 3)
[] [] 1 -1 Both arrays are empty
[1] [2] 2 2 Combined: [1, 2], 2nd element is 2

Solution❯

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the correct partition is found in the first attempt.
Average CaseO(log(min(n, m)))Binary search runs on the smaller array, halving the search space at each step.
Worst CaseO(log(min(n, m)))The binary search continues until all partition points are exhausted on the smaller array.

Space Complexity❯

O(1)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...