Leetcode 378 Solution

This article provides solution to leetcode question 378 (kth-smallest-element-in-a-sorted-matrix)
Categories:
Tags:
Access this page by simply typing in "lcs 378" in your browser address bar if you have bunnylol configured.

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;
    }
};