Median in a row-wise sorted matrix

"""
Since n and m are odd, the total number of elements (N = n * m) is always odd.
suppose we flattened the matrix and sorted them into a 1-d array.In a sorted list of N elements, the median is the middle value at index (n * m) // 2.

The Key Rule:
The median of a sorted 1-d array is the first from left side or (smallest) element where the count of elements
less than or equal that element(means median) is GREATER than the median index ie. (N // 2) means so it can be greater than equal to (N//2)+1

Key rule more refined: The smallest number x such that at least (n*m)//2 + 1 elements are ≤ x.

bisect_left: It returns the first index where an element can be inserted without breaking the sorted order.
bisect_right: It returns the last index where an element can be inserted without breaking the sorted order.

Examples (Total elements N = 9, Median Index = 4):
--------------------------------------------------
1. Standard Case (No duplicates):
   Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
   - Median is 5.
   - count of elements <= 5 is 5. (5 > 4(median index), so this works!)
   - count of elements <= 4 is only 4. (4 is not > 4, so 4 can't be median).

2. Duplicates on the Left (Median is 5):
   Array: [1, 2, 5, 5, 5, 6, 7, 8, 9]
   - Index 4 is the middle '5'.
   - How many elements are <= 5? There are 5 elements.
   - Since 5 > 4, 5 is a candidate for median.

3. Duplicates on Both Sides (Median is 5):
   Array: [1, 5, 5, 5, 5, 5, 5, 5, 9]
   - Index 4 is '5'.
   - How many elements are <= 5? There are 8 elements.
   - Since 8 > 4, 5 is a candidate. We look for the first number
     to satisfy this, which is 5.
   - the number less than 5 and which can be a probable mean have count of numbers <=1 is only 1 which is less than N//2 so it is not possible.

so we will check the numbers between min element and max element of the matrix whose count <= N//2 and that element should be smallest or first from
the left, if it satisfies, we will return it.

Time: O(log(Max-Min) * N * log(M))
Space: O(1)

Trick: Rows can internally sorted but row might not be gloaball sorted eg [[5,6,7],[2,3,4]] so you can't consider the 5 as the left range.
"""

from bisect import bisect_right
class Solution:
    def median(self, mat):
        n=len(mat) #row
        m=len(mat[0]) #col
        low = min(row[0] for row in mat)
        high = max(row[-1] for row in mat)

        req = (n * m) // 2 #this many elements should be smaller than or equal to the median in the array

        while low <= high:
            mid = (low + high) // 2

            cnt = 0
            for row in mat: #traversing on all the rows
                cnt += bisect_right(row, mid)   # count of elements <= mid in all the rows of the matrix

            if cnt <= req: #means the median in right
                low = mid + 1
            else:
                high = mid - 1 #even the condition satisfies, we will keep searching elements in the left, may be some smaller element than current element satisfies the condition.the search will stop when low>right

        return low