Jaspreet singh

Posted on Jun 21

kth smallest element in sorted array

#algorithms #interview #java #leetcode

Problem Statement

Given two sorted arrays arr1[] and arr2[] and an integer k, return the kth smallest element from the combined sorted array.

Brute Force Intuition

In an interview, you can explain it like this:

Since both arrays are sorted, we can merge them similar to Merge Sort. While merging, keep counting elements. The moment we reach the kth element, return it.

Complexity

Time Complexity: O(N + M)
Space Complexity: O(N + M)

Brute Force Code

int[] merged = new int[n + m];

// Merge both arrays

return merged[k - 1];

Moving Towards the Optimal Approach

Notice something interesting:

For Median of Two Sorted Arrays, we partitioned arrays such that:

Left Half | Right Half

For Kth Element:

Exactly k elements must lie on the left side.

The partition idea remains exactly the same.

Pattern Recognition

Whenever you see:

Two Sorted Arrays
Kth Smallest Element
Logarithmic Solution Expected

Think:

Binary Search on Partition

Key Observation

Suppose:

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

We need:

Exactly 5 elements on left side

Partition:

2 3 6 | 7 9

1 4   | 8 10

Left Side:

1 2 3 4 6

contains exactly:

5 elements

Answer becomes:

max(left1, left2)

Optimal Approach

Let:

cut1 = elements taken from arr1
cut2 = k - cut1

Valid partition requires:

left1 <= right2

left2 <= right1

Once valid:

answer = Math.max(left1, left2);

Optimal Java Solution

class Solution {

    public long kthElement(int k,
                           int arr1[],
                           int arr2[]) {

        int n1 = arr1.length;
        int n2 = arr2.length;

        if (n1 > n2)
            return kthElement(k, arr2, arr1);

        int low = Math.max(0, k - n2);
        int high = Math.min(k, n1);

        while (low <= high) {

            int cut1 = low + (high - low) / 2;

            int cut2 = k - cut1;

            int left1 =
                cut1 == 0 ? Integer.MIN_VALUE
                           : arr1[cut1 - 1];

            int left2 =
                cut2 == 0 ? Integer.MIN_VALUE
                           : arr2[cut2 - 1];

            int right1 =
                cut1 == n1 ? Integer.MAX_VALUE
                            : arr1[cut1];

            int right2 =
                cut2 == n2 ? Integer.MAX_VALUE
                            : arr2[cut2];

            if (left1 <= right2 &&
                left2 <= right1) {

                return Math.max(left1, left2);
            }

            else if (left1 > right2) {

                high = cut1 - 1;

            } else {

                low = cut1 + 1;
            }
        }

        return -1;
    }
}

Dry Run

Input

arr1 = [2,3,6,7,9]

arr2 = [1,4,8,10]

k = 5

Need:

5 elements on left side

Partition:

2 3 6 | 7 9

1 4   | 8 10

Check:

6 <= 8 ✓

4 <= 7 ✓

Valid Partition.

Answer:

max(6,4)

= 6

Why This Works?

The kth element is simply:

Largest element among the first k elements

When partition is valid:

Left side contains exactly k elements.

Hence:

max(left1, left2)

becomes the kth element.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(min(N,M)))
Space Complexity	O(1)

Interview One-Liner

Binary search the partition of the smaller array such that exactly k elements lie on the left side and both partitions remain sorted.

Pattern Learned

Two Sorted Arrays
+
Kth Element
+
Logarithmic Requirement

=> Binary Search on Partition

Memory Trick