For counting the number of elements less than or equal, you can do it in O(n) instead of O(n log n). You can basically go through each column of numbers (from left to right), starting at a column size of n, and add up the largest column size that allows every number in the column to be less than or equal to the target. Since you know that the last element in the column is the largest, if that element is less than or equal to the target, then you can immediately add the entire column size to your count and proceed to the next column. On the other hand, if the last element in the column is too big, you reduce your column size by 1. The key insight here is that once an element is too big, all elements to the right of it (in the same row) will also be too big. But once you reduce your column size, that element might still be within bounds, so you just keep running these steps until you reach the end.
this is gold. I was at first taken aback when the brute force algorithm was accepted. In fact I did similar brute force as what you mentioned here, excepting I used list comprehension for flattening the matrix.
There could be cases that the return value is not in the matrix. I think instead of just return count in the first binary search, we need to return the value larger and the value smaller than the mid that is in the matrix. If there is something like 12.1 in the matrix. We may not get the value. But the method are very good and informational.
![Leetcode 378. Kth Smallest Element in a Sorted Matrix [Java]](http://i.ytimg.com/vi/b4mkk8Fk8fs/mqdefault.jpg)
For counting the number of elements less than or equal, you can do it in O(n) instead of O(n log n). You can basically go through each column of numbers (from left to right), starting at a column size of n, and add up the largest column size that allows every number in the column to be less than or equal to the target.
Since you know that the last element in the column is the largest, if that element is less than or equal to the target, then you can immediately add the entire column size to your count and proceed to the next column.
On the other hand, if the last element in the column is too big, you reduce your column size by 1. The key insight here is that once an element is too big, all elements to the right of it (in the same row) will also be too big. But once you reduce your column size, that element might still be within bounds, so you just keep running these steps until you reach the end.
this is gold. I was at first taken aback when the brute force algorithm was accepted. In fact I did similar brute force as what you mentioned here, excepting I used list comprehension for flattening the matrix.
There could be cases that the return value is not in the matrix. I think instead of just return count in the first binary search, we need to return the value larger and the value smaller than the mid that is in the matrix. If there is something like 12.1 in the matrix. We may not get the value. But the method are very good and informational.
where is bisect_right defined ? does not appear to be and I get an error running the code as a result. Am i missing something ?
It's auto imported for leetcode, you can import it from python3 docs.python.org/3/library/bisect.html
What are you doing in the bisect_right part? What is the logic behind that?
Can we just not flatten this 2D list, then sort it and return the kth element? Is something wrong with it?
it works, but is clearly not the optimal solution as it takes O(n^2) time and space