thesarfo

Reference

Kth Element of Two Sorted Arrays

Finding the kth smallest element across two sorted arrays — full merge, two-pointer simulation, and a divide-and-conquer partition approach.

views 0

Find the kth smallest element across two sorted arrays, merged. nums1=[1,3,5], nums2=[2,4,6], k=4 → 4.

Brute force: merge and sort, then index — O((n+m) log(n+m)) time, O(n+m) space.

Better — two-pointer merge simulation: walk both arrays with two pointers, advancing whichever is smaller, until a counter reaches k — O(k) time, O(1) space.

class Solution {
    public int findKthElement(int[] nums1, int[] nums2, int k) {
        int i = 0, j = 0, count = 0;


        while (i < nums1.length && j < nums2.length) {
            int smallerElement;
            if (nums1[i] <= nums2[j]) {
                smallerElement = nums1[i];
                i++;
            } else {
                smallerElement = nums2[j];
                j++;
            }


            count++;
            if (count == k) {
                return smallerElement;
            }
        }


        while (i < nums1.length) {
            count++;
            if (count == k) return nums1[i];
            i++;
        }


        while (j < nums2.length) {
            count++;
            if (count == k) return nums2[j];
            j++;
        }


        return -1;
    }
}

Optimal — binary search / divide and conquer: compare the k/2-th elements of each array’s remaining range; whichever is smaller means its entire first half can be discarded (those elements can’t be the kth), shrinking k by half each round.

class Solution {
    public int findKthElement(int[] nums1, int[] nums2, int k) {
        return findKth(nums1, 0, nums2, 0, k);
    }


    private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j + k - 1];
        if (j >= nums2.length) return nums1[i + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);


        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;


        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
}

Time: O(log k). Space: O(log k) for the recursion stack.