Clean solution with detailed explanation in C++


  • 2

    Solution

    Analysis

    Since the matrix is sorted in two directions, using binary search to find the kth smallest is an intuitive method. Since we are searching for the number, so the searching space should be the space ranging from the smallest to the biggest number in the matrix.

    Note that the index here cannot be used to form the searching space since it's not linear to the numbers in the matrix, whose order lies in two directions unlike the index from 0 to size(size-1).

    Take [[1,4],[3,5]] 2 as an example. If we use the index range as the searching space, l=0, r=3, m=(0+3)/2=1 in the first round and then the numbers smaller than or equal to its number, matrix[m/size][m%size]=matrix[1/2][1%2]=matrix[0][1]=4, are 3 (1, 4 and 3 respectively) and then we will set r=m=1. Just now we have eliminated the potential answer number 3, whose index should be 2 matrix[2/2][2%2]=matrix[1][0]. All of these are because the index sequence is not linear to the matrix numbers whose order lies in two directions.

    Details

    • Start with half of the smallest and biggest of the matrix, and then count how many numbers are smaller than or equal to it row by row;
    • K directly becomes the comparison determining which direction we will go in the next round, left part or the right part;
    • Keep the answer number within the range [l, r] in each round.

    The time complexity will be O(nlognlogm) while n is the number of rows in the matrix and m is the gap between the smallest and the biggest number in the matrix.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) 
        {
            int size = matrix.size(), l = matrix[0][0], r = matrix[size-1][size-1];
            while(l < r)
            {
                int smaller = 0, m = l+((r-l)>>1);
                for(int i = 0; i < size; ++i) 
                    smaller += upper_bound(matrix[i].begin(), matrix[i].end(), m)-matrix[i].begin();
                smaller<k? l=m+1 : r=m;
            }
            return r;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    W
    This post is deleted!

  • 0
    L

    @LHearen said in Clean solution with detailed explanation in C++:

    Solution

    Analysis

    Since the matrix is sorted in two directions, using binary search to find the kth smallest is an intuitive method. Since we are searching for the number, so the searching space should be the space ranging from the smallest to the biggest number in the matrix.

    Note that the index here cannot be used to form the searching space since it's not linear to the numbers in the matrix, whose order lies in two directions unlike the index from 0 to size(size-1).

    Take [[1,4],[3,5]] 2 as an example. If we use the index range as the searching space, l=0, r=3, m=(0+3)/2=1 in the first round and then the numbers smaller than or equal to its number, matrix[m/size][m%size]=matrix[1/2][1%2]=matrix[0][1]=4, are 3 (1, 4 and 3 respectively) and then we will set r=m=1. Just now we have eliminated the potential answer number 3, whose index should be 2 matrix[2/2][2%2]=matrix[1][0]. All of these are because the index sequence is not linear to the matrix numbers whose order lies in two directions.

    Details

    • Start with half of the smallest and biggest of the matrix, and then count how many numbers are smaller than or equal to it row by row;
    • K directly becomes the comparison determining which direction we will go in the next round, left part or the right part;
    • Keep the answer number within the range [l, r] in each round.

    The time complexity will be O(nlognlogm) while n is the number of rows in the matrix and m is the gap between the smallest and the biggest number in the matrix.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) 
        {
            int size = matrix.size(), l = matrix[0][0], r = matrix[size-1][size-1];
            while(l < r)
            {
                int smaller = 0, m = l+((r-l)>>1);
                for(int i = 0; i < size; ++i) 
                    smaller += upper_bound(matrix[i].begin(), matrix[i].end(), m)-matrix[i].begin();
                smaller<k? l=m+1 : r=m;
            }
            return r;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!

    @LHearen said in Clean solution with detailed explanation in C++:

    Solution

    Analysis

    Since the matrix is sorted in two directions, using binary search to find the kth smallest is an intuitive method. Since we are searching for the number, so the searching space should be the space ranging from the smallest to the biggest number in the matrix.

    Note that the index here cannot be used to form the searching space since it's not linear to the numbers in the matrix, whose order lies in two directions unlike the index from 0 to size(size-1).

    Take [[1,4],[3,5]] 2 as an example. If we use the index range as the searching space, l=0, r=3, m=(0+3)/2=1 in the first round and then the numbers smaller than or equal to its number, matrix[m/size][m%size]=matrix[1/2][1%2]=matrix[0][1]=4, are 3 (1, 4 and 3 respectively) and then we will set r=m=1. Just now we have eliminated the potential answer number 3, whose index should be 2 matrix[2/2][2%2]=matrix[1][0]. All of these are because the index sequence is not linear to the matrix numbers whose order lies in two directions.

    Details

    • Start with half of the smallest and biggest of the matrix, and then count how many numbers are smaller than or equal to it row by row;
    • K directly becomes the comparison determining which direction we will go in the next round, left part or the right part;
    • Keep the answer number within the range [l, r] in each round.

    The time complexity will be O(nlognlogm) while n is the number of rows in the matrix and m is the gap between the smallest and the biggest number in the matrix.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) 
        {
            int size = matrix.size(), l = matrix[0][0], r = matrix[size-1][size-1];
            while(l < r)
            {
                int smaller = 0, m = l+((r-l)>>1);
                for(int i = 0; i < size; ++i) 
                    smaller += upper_bound(matrix[i].begin(), matrix[i].end(), m)-matrix[i].begin();
                smaller<k? l=m+1 : r=m;
            }
            return r;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    K

    The way termination " smaller<k? l=m+1 : r=m;" handled is awesome. Kudos for that. I doubted that the algorithm would not handle the case where we would get an "m" for which "smaller" is equal to k and that "m" would not exist in the given matrix. But this is handled in the else part where "smaller==k" would be pushing "m" towards the correct value.


  • 0
    W

    @LHearen Awesome code! I thought I could understand the binary search part, yet still a little confuse here: how to prove that 'r' will finally converge to an integer in the matrix? Thanks for the analysis


  • 2

    @wohenniubi3 r will always include the result while l will become bigger and bigger if the left side is invalid and when it comes to its end, the r can only be the value we are expecting.


  • 0
    W

    @LHearen Thanks for the response. Yet, I still feel that r might not always include the element in the matrix, e.g. in the case [[1, 5, 9],[10, 11, 13], [12,13,15]], k=8, the triple of l.r,m in each iteration could form vector<triple<int, int, int>> l_r_m = [[1,15,8], [9,15,12],[13,15,14],[13,14,13]]. It seems that r can be 14, which is not in the matrix.

    I think the constraints such as "int", "l=m+1", "r=m" and "l<r“ construct a magic way to converge r to the valid result. Let me re-think through your analysis and welcome further discussion. Again, cool code!


  • 1

    @wohenniubi3 As I have mentioned r will be bigger than or equal to the final answer always. In your case, the last triple [13, 14, 13] will cause another iteration since 13 < 14 still; and in that iteration the r = m = 13 will be the expected answer. The magic here is upper_bound which will require the bigger than m always.


  • 1
    W

    @LHearen I see. Similar to your analysis, here is my understanding:
    (1) the result (valid element in the matrix) is always confined within the range [l, r];
    (2) the loop while(l<r) won't stop, and finally in the last but one iteration, l is equal to r-1 due to their integer property.
    If we agree these two premises (1)(2), then before the last iteration, the valid element could only be either r-1 or r, or as you explained, r will be bigger than or equal to the final answer.
    Now before we approach to the final iteration, take a deeper look at the changes of l and r;

    • For the bigger case, l and r are equal to k and k+1, respectively. Then due to the upper_bound trick that applied in the while loop, (smaller<k) is surely false, and r is forced to m(=l+(r-l)/2), which is equal to k; next, the loop of while(l<r) breaks, return r;

    • For the equal case, l and r are equal to k-1 and k, respectively. Still because of the upper_bound trick, (smaller<k) is surely true, and l is forced to become m+1. Since m(=l+(r-l)/2) is equal to k-1, next, the loop of while(l<r) breaks, return r;

    To sum up, besides the smart use of the binary search, the trick of updating l and r, upper_bound, make this code awesome! Thanks again to your help!


  • 0

    @wohenniubi3 The analysis is kind of clear. Thanks for sharing!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.