How hard is LeetCode 2387. Median of a Row Wise Sorted Matrix?

LeetCode 2387. Median of a Row Wise Sorted Matrix is rated Medium on LeetCode.

What is the time complexity of LeetCode 2387. Median of a Row Wise Sorted Matrix?

The Python solution on this page runs in O(m \times \log n \times \log M), where m and n are the number of rows and columns of the grid, respectively, and M is the maximum element in the grid.

What is the space complexity of LeetCode 2387. Median of a Row Wise Sorted Matrix?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2387. Median of a Row Wise Sorted Matrix cover?

LeetCode 2387. Median of a Row Wise Sorted Matrix is tagged Array, Binary Search and Matrix on LeetCode.

Is LeetCode 2387. Median of a Row Wise Sorted Matrix a premium problem?

Yes. LeetCode 2387. Median of a Row Wise Sorted Matrix is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Median of a Row Wise Sorted Matrix — LeetCode 2387 Python Solution

MediumLeetCode PremiumArrayBinary SearchMatrix

Problem: #2387
Pattern: Matrix and Grid
Reading time: 2 min
Source: leetcode.com

The problem

Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix. You must solve the problem in less than O(m * n) time complexity.

Example

Input: grid = [[1,1,2],[2,3,3],[1,3,4]]
Output: 2
Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.

Python solution

Python

class Solution:
    def matrixMedian(self, grid: List[List[int]]) -> int:
        def count(x):
            return sum(bisect_right(row, x) for row in grid)

        m, n = len(grid), len(grid[0])
        target = (m * n + 1) >> 1
        return bisect_left(range(10**6 + 1), target, key=count)

Complexity

Measure	Complexity
Time	O(m \times \log n \times \log M), where m and n are the number of rows and columns of the grid, respectively, and M is the maximum element in the grid
Space	O(1) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2387. Median of a Row Wise Sorted Matrix is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2387. Median of a Row Wise Sorted Matrix?: LeetCode 2387. Median of a Row Wise Sorted Matrix is rated Medium on LeetCode.
What is the time complexity of LeetCode 2387. Median of a Row Wise Sorted Matrix?: The Python solution on this page runs in O(m \times \log n \times \log M), where m and n are the number of rows and columns of the grid, respectively, and M is the maximum element in the grid.
What is the space complexity of LeetCode 2387. Median of a Row Wise Sorted Matrix?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2387. Median of a Row Wise Sorted Matrix cover?: LeetCode 2387. Median of a Row Wise Sorted Matrix is tagged Array, Binary Search and Matrix on LeetCode.
Is LeetCode 2387. Median of a Row Wise Sorted Matrix a premium problem?: Yes. LeetCode 2387. Median of a Row Wise Sorted Matrix is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.