[Hard] interview questions #24

[rygh4775]

Max Submatrix: Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

[rygh4775]

Solution#1

Brute force

1. Iterate through all possible submatrices
2. Compute the sum
3. Finds the largest

int getMaxMatrixSum(int[][] matrix) {
  int best;
  int rowCount = matrix.length;
  int columnCount = matrix[0].length;

  for(int row1 = 0; row1 < rowCount; row1++) {
    for(int row2 = row1; row2 < rowCount; row2++) {
      for(int col1 = 0; col1 < columnCount; col1++) {
        for(int col2 = 0; col2 < columnCount; col2++) {
          int sum = sum(matrix, row1, col1, row2, col2);
          if (sum > best) {
            best = sum;
          }
        }
      }
    }
  }
  return best;
}

int sum(int[][] matrix, int row1, int col1, int row2, int col2) {
  int sum;
  for(int r = row1; r <= row2; r++) {
    for(int c = col1; c <= col2; c++) {
      sum += matrix[r][c];
    } 
  }
  return sum;
}

• Time complexity

  O(N⁶), N is the length of matrix

Solution#2

• area(D) = through(D) - through(B) - through(C) + through(A)

  
  int getMaxMatrixSum(int[][] matrix) {
  int best;
  int rowCount = matrix.length;
  int columnCount = matrix[0].length;
  int[][] sumThrough = precomputeSums(matrix);
  
  for(int row1 = 0; row1 < rowCount; row1++) {
  for(int row2 = row1; row2 < rowCount; row2++) {
    for(int col1 = 0; col1 < columnCount; col1++) {
      for(int col2 = 0; col2 < columnCount; col2++) {
        int sum = sum(sumThrough, row1, col1, row2, col2);
        if (sum > best) {
          best = sum;
        }
      }
    }
  }
  }
  return best;
  }

int precomputeSums(int[][] matrix) { int[][] sumThrough = new int[matrix.length][matrix[0].length; for(int r = 0; r < matrix.length; r++) { for(int c = 0; c < matrix[0].length; c++ { int left = c > 0 ? sumThrough[r][c-1] : 0; int top = r > 0 ? sumThrough[r-1][c] : 0; int overlap = (r > 0 && c > 0) ? sumThrough[r-1][c-1] : 0; sumThrough[r][c] = left + top - overlap + matrix[r][c]; } } return sumThrough; }

int sum(int[][] sumThrough, int r1, int c1, int r2, int c2) { int full = sumThrough[r2][c2]; int left = c1 > 0 ? sumThrough[r2][c1-1] : 0; int top = r1 > 0 ? sumThrough[r1-1][c2] : 0; int topAndLeft = (r1 > 0 && c1 > 0) ? sumThrough[r1-1][c1-1] : 0; return full - left - top + topAndLeft; }

- Time complexity

  O(N<sup>4</sup>), N is the length of matrix