30ms JAVA o(mn) time, o(n) space, beat 99.9%


  • 0
    J

    The solution is basically traversing twice. Firstly traverse from top to bottom, from left to right. And the second is to traverse from bottom to top, from right to left.

    During the two traversing, we collect row_count_of_enemies, column_count_of_enemies using o(1) time. I use a rowCount to collect enemies in this row, and using array col[] to collect enemies in the col, here uses o(n) space. (firstly from top to bottom, secondly from bottom to top.)

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            int n = grid.length;
            if (n<1) return n;
            int m = grid[0].length;
            // calculate how many enimies on the column
            int[] col = new int[m]; 
            int max_enemies = 0;
            //from up to down, left to right
            for (int i=0; i<n; i++) {
                int rowCount = 0;
                for (int j=0; j<m; j++) {
                    char ch = grid[i][j];
                    if (ch=='W') {
                        rowCount = 0;
                        col[j] = 0;
                    }
                    else if (ch=='E') {
                        rowCount++;
                        col[j]++;
                    }
                    else if (ch == '0') {
                      // Change the start point to X, Otherwise, number+"0" might be W or E
                        grid[i][j] = (char)('X'+ rowCount + col[j]); 
                    }
                }
            }
          // Now it accumulate enemies from bottom to current row
            col = new int[m];
            // from bottom up, right left
            for (int i=n-1; i>=0; i--) {
                int rowCount = 0;  // count from right
                for (int j=m-1; j>=0; j--) {
                    char ch = grid[i][j];
                    if (ch=='W') {
                        rowCount = 0;
                        col[j] = 0;
                    }
                    else if (ch=='E') {
                        rowCount++; col[j]++;
                    }
                    else {
                        grid[i][j] += rowCount + col[j];
                        max_enemies = Math.max(max_enemies, grid[i][j]-'X');
                        
                    }
                }
            }
            
           return max_enemies; 
        }
    }
    

Log in to reply
 

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