FastPrepPartition Matrix by Nonnegative Averages

Partition Matrix by Nonnegative Averages

TikTok logoTikTok● MediumNEW GRADOA
Learn

Problem statement

You are given an integer matrix with at least two rows and two columns. Choose a row index r and a column index c that divide the matrix into four non-empty rectangular regions:

  • top-left: rows 0 through r and columns 0 through c;
  • top-right: rows 0 through r and columns c + 1 through the last column;
  • bottom-left: rows r + 1 through the last row and columns 0 through c;
  • bottom-right: rows r + 1 through the last row and columns c + 1 through the last column.

For each region, ignore negative entries and compute the floor of the average of its nonnegative entries. A split is valid only when every region contains at least one nonnegative entry.

Minimize the difference between the largest and smallest of the four floored averages. If several splits have the same minimum difference, return the one with the smallest r, then the smallest c.

Return [r, c].

Function

findBestPartition(matrix: int[][]) → int[]

Examples

Example 1

matrix = [[1,2,3],[4,5,6],[7,8,9]]return = [0,0]

The splits at [0,0], [1,0], and [1,1] each have range 6, the minimum possible range. The row-then-column tie rule selects [0,0].

Example 2

matrix = [[0,10],[4,8]]return = [0,0]

The only split creates four one-cell regions, all with nonnegative entries, so the result is [0,0].

Constraints

  • 2 <= matrix.length <= 200
  • 2 <= matrix[i].length <= 200
  • Every row has the same length.
  • -10^9 <= matrix[i][j] <= 10^9
  • At least one valid split exists.

More TikTok problems

See TikTok hiring insights
public int[] findBestPartition(int[][] matrix) {
  // write your code here
}
matrix[[1,2,3],[4,5,6],[7,8,9]]
expected[0,0]
Checking account…