Not understanding why this is a poor solution...


  • 0

    So, I came up with a solution which seems like it should be pretty decent, but it's not accepted due to failing the time limit.

    I can see how this is definitely not the ideal solution -- e.g. there are some solutions making clever use of various data structures that are definitely better. But when I came up with this it seemed like a perfectly reasonable DP approach, and I'm wondering if my intuition is just totally off here, and if so, why.

    The basic intuition is to build up a list of the sums of rectangles from 0,0 to x,y, and then find the values of all other rectangles by adding and subtracting those sums. So, unless I'm missing something, this should be O(m²n²) for an m x n matrix, as each sum is calculated in O(1).

    Here it is:

    public class Solution {
        private Integer[][] sums;
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int width = matrix.length;
            int height = matrix[0].length;
            this.sums = new Integer[matrix.length][matrix[0].length];
            int max = -2147483648;
            if (max == k) {
                return k;
            }
            for (int y1=0; y1<height; y1++) {
                for (int x1=0; x1<width; x1++) {
                    for (int y2=y1; y2<height; y2++) {
                        for (int x2=x1; x2<width; x2++) {
                            int sum = this.sumTo(matrix, x2, y2)
                                    - this.sumTo(matrix, (x1-1), y2)
                                    - this.sumTo(matrix, x2, (y1-1))
                                    + this.sumTo(matrix, (x1-1), (y1-1));
                            if ((sum > max) && (sum <= k)) {
                                max = sum;
                            }
                            if (max == k) {
                                return k; 
                            }
                        }
                    }
                }
            }
            return max;
        }
        
        public int sumTo(int[][] mat, int x, int y) {
            if ((x<0) || (y<0)) {
                return 0;
            }
            if (this.sums[x][y] == null) {
                this.sums[x][y] = mat[x][y]
                                + this.sumTo(mat, x-1, y)
                                + this.sumTo(mat, x, y-1)
                                - this.sumTo(mat, x-1, y-1);
            }
            return this.sums[x][y];
        }
    }
    

  • 0

    @ThatsMyBrain Your solution is alright, but quite inefficient, check this post


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.