Time limit exceeding on the most efficient approach :(


  • 0
    S

    My code is exceeding the time limit, even though, on referring to the editorial solution, I found that my implementation is the most efficient one (that involving caching region sums i.e. Approach #4 (Caching Smarter))

    Could someone please review what could be going wrong. The time complexity of the pre-computation step is O(mn) and space complexity is O(mn) too. All queries take O(1) time.

    public class NumMatrix {
        int sum[][] = null;
        public NumMatrix(int[][] matrix) {
            if(matrix.length > 0){
                int rows = matrix.length;
                int cols = matrix[0].length;
                sum = new int[rows][cols];  
                sum[0][0] = matrix[0][0];
                for(int col = 1; col < cols ; col++ ){
                    sum[0][col] = sum[0][col-1] + matrix[0][col];
                }
                for(int row = 1; row < rows ; row++ ){
                    sum[row][0] = sum[row-1][0] + matrix[row][0];
                }
             
                for(int row = 1; row < rows ; row++ )
                 for(int col = 1; col < cols ; col++ ){
                     sum[row][col] = sum[row-1][col] + sum[row][col-1] - sum[row-1][col-1] + matrix[row][col];
                }
            }
            
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            if(sum == null){
                return 0;
            }
            int prev = 0;
            int x = 0;
            int y = 0;
            if(row1 > 0 && col1 > 0){
                prev = sum[row1-1][col1-1];
            }
            x = (row1 > 0) ? sum[row1-1][col2]: 0;
            y = (col1 > 0) ? sum[row2][col1-1]: 0;
            return sum[row2][col2] - (x + y - prev);
        }
    }
    
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix = new NumMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.sumRegion(1, 2, 3, 4);

Log in to reply
 

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