Loading...
Loading...
You are given an m x n integer matrix matrix. You cut it once horizontally and once vertically, which splits it into four non-empty quadrants.
A cut is written as [r, c], where 1 <= r <= m - 1 and 1 <= c <= n - 1. Rows 0 to r - 1 form the top half and rows r to m - 1 form the bottom half. Columns 0 to c - 1 form the left half and columns c to n - 1 form the right half.
Negative cells are ignored. The average of a quadrant is the sum of its non-negative cells divided by the number of its non-negative cells, rounded down. Note that 0 is non-negative, so a cell holding 0 counts.
A cut is valid only if each of its four quadrants contains at least one non-negative cell. The spread of a valid cut is its largest quadrant average minus its smallest quadrant average.
Return the valid cut [r, c] with the smallest spread. If several valid cuts share the smallest spread, break the tie in this order:
r wins;c wins.If no cut is valid, return [-1, -1].
Input: matrix = [[2, 7, 1, 4],
[6, 3, 8, 5],
[9, 1, 2, 6]]
Output: [2, 2]
Explanation: The cut [2, 2] makes a top-left quadrant [[2,7],[6,3]], a top-right quadrant [[1,4],[8,5]], a bottom-left quadrant [[9,1]] and a bottom-right quadrant [[2,6]]. Their sums are 18, 18, 10 and 8 over 4, 4, 2 and 2 cells, so their averages are 4, 4, 5 and 4 (18 / 4 = 4.5 rounds down to 4). The spread is 5 - 4 = 1. Every other cut has a spread of at least 2.
Input: matrix = [[1, 7, 2],
[6, 2, 4],
[3, 3, 0]]
Output: [1, 2]
Explanation: The cut [1, 2] has top-left, top-right, bottom-left and bottom-right averages 4, 2, 3 and 2, so its spread is 4 - 2 = 2. Its bottom-right quadrant is [[4],[0]]: the 0 counts, so the average is 4 / 2 = 2. The cut [2, 1] has averages 3, 3, 3 and 1, also a spread of 2. No cut does better. Of the two tied cuts, [1, 2] has the smaller row, so it wins.
Input: matrix = [[ 4, -2, 6],
[-7, 1, 3],
[ 8, 5, -9]]
Output: [1, 2]
Explanation: For the cut [1, 2], the bottom-left quadrant is [[-7,1],[8,5]]. The -7 is ignored, so its average is (1 + 8 + 5) / 3 = 4 after rounding down. The four averages (top-left, top-right, bottom-left, bottom-right) are 4, 6, 4 and 3, a spread of 3. The cuts [1, 1] and [2, 1] both have a spread of 5. The cut [2, 2] is not valid: its bottom-right quadrant holds only -9.
Input: matrix = [[ 7, -4, 2],
[-5, -8, -1]]
Output: [-1, -1]
Explanation: Every cut puts the whole second row in the bottom half, and that row has no non-negative cell. No cut is valid.
matrix.length and n= matrix[i].lengthmatrix[i][j] ≤104