FastPrepSplit a Matrix by Nonnegative Region Averages

Split a Matrix by Nonnegative Region Averages

Susquehanna International Group (SIG) logoSusquehanna International Group (SIG)● MediumFULLTIMEOA

Problem statement

You are given a rectangular integer matrix. Choose a row index r and a column index c that split it into four nonempty rectangular regions:

  • Top-left: rows 0..r, columns 0..c.
  • Top-right: rows 0..r, columns c+1..cols-1.
  • Bottom-left: rows r+1..rows-1, columns 0..c.
  • Bottom-right: rows r+1..rows-1, columns c+1..cols-1.

For each region, ignore all negative entries and take the floor of the average of its nonnegative entries. Zero is included. A split is valid only if every region contains at least one nonnegative entry.

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

Return [r,c]. At least one valid split is guaranteed to exist.

Function

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

Examples

Example 1

matrix = [[7,9,-1,-1],[3,8,-1,-1],[5,5,7,-1]]return = [1,0]

At [1,0], the floored region averages are 5,8,5,6, giving difference 3. Negative entries are excluded. No valid split has a smaller difference.

Example 2

matrix = [[0,0,0],[0,0,0],[0,0,0]]return = [0,0]

Every split has four zero averages. The smallest row and then column give [0,0].

Constraints

  • 2 <= rows, cols <= 200.
  • Every row has exactly cols entries.
  • -10^9 <= matrix[i][j] <= 10^9.
  • At least one split has a nonnegative entry in each of its four regions.

More Susquehanna International Group (SIG) problems

See Susquehanna International Group (SIG) hiring insights
Saved
public int[] bestMatrixSplit(int[][] matrix) {
    // Write your code here.
}
matrix[[7,9,-1,-1],[3,8,-1,-1],[5,5,7,-1]]
expected[1,0]
Checking account…