2 Accepted Java Solution


  • 24
    A

    Decide to post because I was actually asked this question during my interview!
    There is a simple version of O(n^4).
    The idea is to calculate every rectangle [[r1,c1], [r2,c2]], and simply pick the max area <= k.
    An improved version takes O(n^3logn). It borrows the idea to find max subarray with sum <= k in 1D array, and apply here: we find all rectangles bounded between r1 & r2, with columns from 0 to end. Pick a pair from tree.
    I remember the interviewer said there could be an even better solution, but I haven't figured that out...

    Solution I, O(n^4):

    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] areas = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int area = matrix[r][c];
                if (r-1 >= 0)
                    area += areas[r-1][c];
                if (c-1 >= 0)
                    area += areas[r][c-1];
                if (r-1 >= 0 && c-1 >= 0)
                    area -= areas[r-1][c-1];
                areas[r][c] = area;
            }
        }
        int max = Integer.MIN_VALUE;
        for (int r1 = 0; r1 < rows; r1++) {
            for (int c1 = 0; c1 < cols; c1++) {
                for (int r2 = r1; r2 < rows; r2++) {
                    for (int c2 = c1; c2 < cols; c2++) {
                        int area = areas[r2][c2];
                        if (r1-1 >= 0)
                            area -= areas[r1-1][c2];
                        if (c1-1 >= 0)
                            area -= areas[r2][c1-1];
                        if (r1-1 >= 0 && c1 -1 >= 0)
                            area += areas[r1-1][c1-1];
                        if (area <= k)
                            max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
    

    Solution II (O(n^3logn)

    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] areas = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int area = matrix[r][c];
                if (r-1 >= 0)
                    area += areas[r-1][c];
                if (c-1 >= 0)
                    area += areas[r][c-1];
                if (r-1 >= 0 && c-1 >= 0)
                    area -= areas[r-1][c-1];
                areas[r][c] = area;
            }
        }
        int max = Integer.MIN_VALUE;
        for (int r1 = 0; r1 < rows; r1++) {
            for (int r2 = r1; r2 < rows; r2++) {
                TreeSet<Integer> tree = new TreeSet<>();
                tree.add(0);    // padding
                for (int c = 0; c < cols; c++) {
                    int area = areas[r2][c];
                    if (r1-1 >= 0)
                        area -= areas[r1-1][c];
                    Integer ceiling = tree.ceiling(area - k);
                    if (ceiling != null)
                        max = Math.max(max, area - ceiling);
                    tree.add(area);
                }
            }
        }
        return max;
    }

  • 0
    J

    Were you asked this question in phone interview or onsite? And may I ask what result you got?


  • 0
    A

    During on-site. I gave the result as posted :)


  • 0
    A

    hi, why we need this step " tree.add(0); // padding" ?


  • 2
    A

    to get area of a rectangle, i use a large area to subtract a smaller area on the left.
    we add a padding area of 0 to enable the case where the large area is the rectangle without a smaller area on the left to subtract; that is, the rectangle's left column is column 0.


  • 0
    D

    I was gave this question in phone interview...........


  • 0
    A

    you truly interviewed like a boss.


  • 0
    Y

    Nice solution! I think the only improvement is to consider the difference between number of rows and cols.


  • 0
    M

    The second solution is not getting accepted. I just copy pasted the code, and I am getting "Time Limit Exceeded".


  • 0
    A

    @mishrasonu1993 : I just tried and it seems to be accepted. Maybe you can try resubmit?


  • 1
    H

    I converted 2 solutions to C++ and found both of them got TLE. Seems judge has more strict time requirement to C++ implementation.


  • 0
    N

    @april.rongchen not sure whether someone has replied to you. Anyhow, here is my thought:
    with that padding, you will not miss the case when area == k.


  • 0
    R

    Great idea for transferring this problem to 1D sub array problem! But any idea why the n^3logn solution costs much more time than dp solution? For my submission, dp(n^4) cost 230ms, while n^3logn costs 700+ms


  • 0
    C
    This post is deleted!

Log in to reply
 

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