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

You are given an n x n matrix in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom (duplicate values are allowed). Given an integer k, find the k-th smallest element in the matrix (1-indexed) by binary searching over the range of possible values and, for each candidate value, using an O(n) staircase-counting search to determine how many matrix elements are less than or equal to it.

Input: The first line contains two integers n and k. Each of the next n lines contains n space-separated integers, the matrix rows. Output: Print a single integer: the k-th smallest element in the matrix.

1 <= n <= 1000 1 <= k <= n*n -10^9 <= matrix[i][j] <= 10^9 Each row is non-decreasing left to right; each column is non-decreasing top to bottom.

This combines TWO techniques already seen elsewhere in this category: binary search on the ANSWER (a value, not an index) and the staircase COUNTING walk - recognizing how previously-learned techniques COMBINE to solve a harder problem is a valuable, transferable skill.

Find the kth smallest value in a matrix sorted both by row and by column, using binary search over values combined with an efficient counting technique. Brute force: Flatten the matrix into one array, sort it, and index directly into the kth position - this costs O(n² log(n²)) for the sort, ignoring the matrix's already-sorted row/column structure entirely. Optimised: Binary searching over the VALUE range (not indices) and using the staircase technique to count 'how many elements are <= v' in O(n) per candidate (exploiting both row AND column sortedness simultaneously) avoids ever building or sorting a flattened array - each binary search step costs just O(n), giving O(n log(value range)) overall.

1. Binary search on the VALUE (not the index): the search range is [matrix[0][0], matrix[n-1][n-1]] (the smallest and largest possible values). 2. For a candidate value v, count how many elements are <= v in O(n) using a STAIRCASE walk: start at the top-right corner, step LEFT when the current cell EXCEEDS v, or step DOWN (adding the whole row up to the current column) when it doesn't. 3. The smallest value v for which that count is >= k is GUARANTEED to actually be present in the matrix - that value is the answer.

Time: O(n log(maxValue - minValue)) - each of the O(log(value range)) binary search steps costs O(n) for the staircase count. Space: O(1) extra space beyond the input matrix.

k = 1 (the smallest element, matrix[0][0]) and k = n*n (the largest element, matrix[n-1][n-1]); matrices containing duplicate values.

Be ready to explain why the staircase counting walk (starting top-right, moving left or down) achieves O(n) per count - it's the exact same technique as 'Search in a Sorted 2D Matrix', just repurposed here to COUNT elements below a threshold rather than to find one specific target.