n^3 * Log(n) solution with build sum array on the fly


  • 0
    D

    Understand the tree set ceiling operation is Log(n) to previous accumulation sum

    public class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        final int N = matrix.length;
        final int M = N == 0 ? 0 : matrix[0].length;
        int max = Integer.MIN_VALUE;
        for(int r1 = 0; r1 < N; ++r1){
            int tmp[] = new int[M];
            for(int r2 = r1; r2 < N; ++r2){
                // here the problem change to 
                // find the max sum of subarray which is less or equal than k
                // Use tree set find ceil is O(logn)
                TreeSet<Integer> ts = new TreeSet<>();
                // for (r1,c) to (r2,c)
                ts.add(0);
                int sum = 0;
                for(int c = 0; c < M; ++c){
                   tmp[c] += matrix[r2][c];
                   // O(logn) operation
                   sum += tmp[c];
                   Integer ceil = ts.ceiling(sum - k);
                   if(ceil != null){
                        if(sum - ceil == k) return k;
                        max = Math.max(max, sum - ceil);
                   }
                   ts.add(sum);
                }
            }  
        }
        return max;
    }
    }

Log in to reply
 

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