Problem Statement

Given a sorted matrix of integers A of size N x M and an integer B.

Each of the rows and columns of matrix A is sorted in ascending order, find the Bth smallest element in the matrix.

NOTE: Return The Bth smallest element in the sorted order, not the Bth distinct element.

Problem Constraints

1 <= N, M <= 500

1 <= A[i] <= 109

1 <= B <= N * M

Input Format

The first argument given is the integer matrix A.

The second argument given is an integer B.

Output Format

Return the B-th smallest element in the matrix.

Example Input

Input 1:

 A = [ [9, 11, 15],
       [10, 15, 17] ]
 B = 6

Output 1:

 17

Explanation 1:

 6th smallest element in the sorted matrix is 17.

Input 2:

 A = [  [5, 9, 11],
        [9, 11, 13],
        [10, 12, 15],
        [13, 14, 16],
        [16, 20, 21] ]
 B = 12

Output 2:

 16

Explanation 2:

 12th smallest element in the sorted matrix is 16.

Solution

solve(A,B)

1. Initialization:

   • Initialize low to the minimum element in the matrix (top-left corner).
   • Initialize high to the maximum element in the matrix (bottom-right corner).

2. Binary Search Loop:

   • The function uses a binary search loop, where it continues to search for the Bth smallest element until low is no longer less than high.
   • In each iteration, it calculates the mid value as the midpoint between low and high.

3. Count Elements Less than or Equal to mid:

   • Call the countLessEqual function to count how many elements in the matrix are less than or equal to mid.

4. Adjust Search Space:

   • If the count is less than B, it means that the Bth smallest element is in the right half of the current search space. Therefore, update low = mid + 1.
   • If the count is greater than or equal to B, it means that the Bth smallest element is in the left half of the current search space. Therefore, update high = mid.

5. Exit the Loop:

   • The loop continues until low is no longer less than high.

6. Return Result:

   • The function returns the final value of low, which represents the Bth smallest element in the matrix.

   countLessEqual(matrix, mid)

   The countLessEqual function essentially simulates the process of finding the count of elements less than or equal to a given value (mid) in a partially sorted matrix. This count is then used in the binary search algorithm to adjust the search space.

   1. Initialize count to 0, row to the last row index, and col to 0.
   2. Use a while loop to traverse the matrix:
      • If the current element (matrix[row][col]) is less than or equal to mid:
        • Increment count by the number of elements in the current column (up to the current row).
        • Move to the next column (col++).
      • If the current element is greater than mid:
        • Move to the previous row in the same column (row--).
   3. Return the final count.

   The countLessEqual function essentially simulates the process of finding the count of elements less than or equal to a given value (mid) in a partially sorted matrix. This count is then used in the binary search algorithm to adjust the search space.

Code

solve: function (A, B) {
	const rows = A.length;
	const cols = A[0].length;
	let low = A[0][0];
	let high = A[rows - 1][cols - 1];

        while (low < high) {
            const mid = low + Math.floor((high - low) / 2);
            const count = countLessEqual(A, mid);

            if (count < B) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }

function countLessEqual(matrix, mid) {
    let count = 0;
    const rows = matrix.length;
    const cols = matrix[0].length;
    let row = rows - 1;
    let col = 0;

    while (row >= 0 && col < cols) {
						// If matrix[row][col] is less than or equal to mid,
            // then all elements in the current column (up to the row)
            // are less than or equal to mid.
        if (matrix[row][col] <= mid) {
            count += row + 1;
            col++;
        } else {
						// If matrix[row][col] is greater than mid,
            // move to the previous row in the same column.
            row--;
        }
    }

    return count;
}