44. Kth Smallest Element in a Row-Wise and Column-Wise Sorted Matrix

Given an n x n matrix where every row and every column is sorted ascending, and a value k, find the kth smallest element in the matrix (1-indexed). Print that value.

Input: The first line contains n and k, space-separated. The next n lines each contain n space-separated integers, forming a matrix sorted ascending along both rows and columns. Output: Print a single integer - the kth smallest element in the matrix.

1 <= n <= 300, 1 <= k <= n*n

This is structurally the same 'merge k sorted lists' pattern used elsewhere in DSA (each row IS a sorted list) - recognizing this connection lets the same min-heap-based merging technique transfer directly to that broader problem family.

In a grid where every row AND every column is sorted, find the kth smallest value overall. Brute force: Flatten the entire matrix into one big list and sort it, then index directly to the kth position - this always works correctly and is simple to reason about, though it doesn't take advantage of the matrix's ALREADY-sorted row/column structure at all. Optimised: Since every row is individually already sorted, a min-heap seeded with just the FIRST element of each row always has the GLOBAL smallest remaining candidate at its top - popping and replacing with each row's next element, one step at a time, efficiently 'merges' all the sorted rows together without ever needing a full flatten-and-sort, stopping as soon as you've popped k times.

Push the first element of every row, along with its row and column index, into a min-heap. Repeatedly pop the smallest element k times, and each time an element is popped from row r, push the next element of row r into the heap if one exists. The kth pop is the answer. This exploits the fact that each row is already sorted, so only one 'frontier' candidate per row ever needs to sit in the heap at once, avoiding sorting the whole matrix. Time: O(k log n) Space: O(n)

Binary search over the range of possible values, from matrix[0][0] to matrix[n-1][n-1]. For each candidate mid value, count how many matrix elements are less than or equal to mid in O(n) using the staircase technique: start at the bottom-left corner, move up a row whenever the current element is too big, and move right (adding the whole column above the current cell to the count) otherwise. Narrow the binary search based on whether that count is at least k; the smallest value whose count reaches k is the kth smallest element. Time: O(n log(max-min)) Space: O(1)

Flatten the n x n matrix into a single array containing all n^2 elements, sort that array, and return the element at index k-1. This ignores the row and column sortedness entirely and just solves the general 'kth smallest of n^2 numbers' problem from scratch. Time: O(n^2 log(n^2)) Space: O(n^2)

1. Start a min-priority-queue (min-heap) seeded with just the FIRST element of every single row, since those are each row's smallest candidate. 2. Repeatedly pop the smallest value from the heap - each time you pop one, push in its immediate NEXT neighbor from the same row (if one exists), since that's now the new smallest unconsidered candidate from that row. 3. Do this popping k times total - the kth value popped is the kth smallest element in the entire matrix.

Time: O(k log r), where r is the number of rows - each of the k pop-and-push operations costs O(log r) time on a heap sized to the number of rows. Space: O(r), for the heap holding at most one candidate per row at any given time.

k = 1 (should return the top-left element); k = n*n (should return the overall maximum, at the bottom-right); and n = 300 (largest, confirming the min-heap approach is efficient enough).

Be ready to explain why seeding the heap with just the FIRST element of each row (not the whole matrix) is sufficient - each row's own sorted order guarantees its next-smallest candidate is always immediately available once the current one is popped.