Leetcode 378 Solution

This article provides solution to leetcode question 378 (kth-smallest-element-in-a-sorted-matrix)

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

Solution

class Solution { public: int search_less_or_equal(vector<vector<int>>& matrix, int x) { int res = 0; int m = matrix.size(); int n = matrix[0].size(); int i = m - 1; int j = 0;
while (j < n && i >= 0) { if (matrix[i][j] > x) { i--; } else { j++; res += i + 1; } }
return res; }
int kthSmallest(vector<vector<int>>& matrix, int k) { int l = matrix[0][0]; int r = matrix.back().back();
while (l <= r) { int m = (r - l) / 2 + l;
int cnt = search_less_or_equal(matrix, m);
if (cnt >= k) r = m - 1; else l = m + 1; }
return l; } };