K-th Element of Two Sorted Arrays

Problem Statement

Given two sorted arrays arr1 and arr2 of sizes n and m respectively, find the element that would be at the kth position of the final sorted array formed by merging the two arrays.

Constraints:

• 1 ≤ n, m ≤ 10^6
• 1 ≤ k ≤ n + m
• 0 ≤ arr1[i], arr2[i] ≤ 10^9

Example:

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

Example 2:

• Input: arr1 = [100, 112, 256, 349, 770], arr2 = [72, 86, 113, 119, 265, 445, 892], k = 7
• Output: 256

Approach 1: Brute Force (Merge and Find)

Intuition

Merge both sorted arrays into one sorted array and directly access the kth element.

Algorithm

1. Create a merged array of size n + m
2. Use two pointers to merge both sorted arrays
3. Return the kth element (0-indexed: k-1)

public class Solution {
    public int kthElement(int[] arr1, int[] arr2, int k) {
        int n = arr1.length, m = arr2.length;
        int[] merged = new int[n + m];
        
        int i = 0, j = 0, idx = 0;
        
        while (i < n && j < m) {
            if (arr1[i] <= arr2[j]) {
                merged[idx++] = arr1[i++];
            } else {
                merged[idx++] = arr2[j++];
            }
        }
        
        while (i < n) merged[idx++] = arr1[i++];
        while (j < m) merged[idx++] = arr2[j++];
        
        return merged[k - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n + m) - Merging both arrays
• Space Complexity: O(n + m) - Storing merged array

Approach 2: Merge Until K (Space Optimized)

Intuition

We don't need to merge the entire array. Just merge until we reach the kth element.

Time: O(k), Space: O(1)

Approach 3: Binary Search (Optimal)

Intuition

Use binary search to partition both arrays such that left partitions together contain exactly k elements, and all elements in left partitions are smaller than all elements in right partitions.

Key Observations:

1. We need to find a valid partition of k elements from both arrays
2. If we take cut1 elements from arr1, we need cut2 = k - cut1 from arr2
3. Valid partition: max(left parts) ≤ min(right parts)
4. Binary search on the smaller array for efficiency

Algorithm

1. Ensure arr1 is the smaller array
2. Binary search for cut1 in range [max(0, k-m), min(k, n)]
3. cut2 = k - cut1
4. Check if partition is valid using boundary elements
5. Adjust search space based on comparison

public class Solution {
    public int kthElement(int[] arr1, int[] arr2, int k) {
        int n = arr1.length, m = arr2.length;
        
        // Ensure arr1 is smaller
        if (n > m) {
            return kthElement(arr2, arr1, k);
        }
        
        // Binary search on arr1
        int low = Math.max(0, k - m);  // Minimum elements from arr1
        int high = Math.min(k, n);      // Maximum elements from arr1
        
        while (low <= high) {
            int cut1 = low + (high - low) / 2;
            int cut2 = k - cut1;
            
            // Left and right elements of both partitions
            int left1 = (cut1 == 0) ? Integer.MIN_VALUE : arr1[cut1 - 1];
            int left2 = (cut2 == 0) ? Integer.MIN_VALUE : arr2[cut2 - 1];
            int right1 = (cut1 == n) ? Integer.MAX_VALUE : arr1[cut1];
            int right2 = (cut2 == m) ? Integer.MAX_VALUE : arr2[cut2];
            
            // Valid partition found
            if (left1 <= right2 && left2 <= right1) {
                return Math.max(left1, left2);
            }
            // Too many elements from arr1
            else if (left1 > right2) {
                high = cut1 - 1;
            }
            // Too few elements from arr1
            else {
                low = cut1 + 1;
            }
        }
        
        return -1; // Should never reach here
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(log(min(n, m))) - Binary search on smaller array
• Space Complexity: O(1) - Only using pointers

Relation to Median of Two Sorted Arrays

Finding the kth element is a generalization of finding the median:

Key Takeaways

1. Binary Search on Partition: Instead of searching for a value, search for a valid partition
2. Search on Smaller Array: Binary search on the smaller array for O(log(min(n,m)))
3. Boundary Elements: Use INT_MIN and INT_MAX for edge cases when partition is at boundaries
4. Partition Validity: left1 ≤ right2 AND left2 ≤ right1
5. Search Space: [max(0, k-m), min(k, n)] ensures valid cut2 values
6. Median Connection: Median is just finding k = (n+m)/2 and (n+m)/2+1
7. No Extra Space: Optimal solution uses only O(1) space