O(nm) Java solution, beats 100%


  • 0
    K

    Two times through the grid, adding all the E's to the top and left of the current cell the first time and then adding all the E's to the right and bottom of the current cell the second time.

    class Solution {
        public int maxKilledEnemies(char[][] grid) {
            int n = grid.length;
            if (n == 0) return 0;
            int m = grid[0].length;
            if (m == 0) return 0;
            
            int rowEnemiesCount = 0;
            int[] colEnemiesCounts = new int[m];
            
            for (int r = 0; r < n; r ++) {
                for (int c = 0; c < m; c ++) {
                    switch(grid[r][c]) {
                        case 'E':
                            rowEnemiesCount ++;
                            colEnemiesCounts[c] ++ ;
                            break;
                        case 'W':
                            rowEnemiesCount = 0;
                            colEnemiesCounts[c] = 0;
                            break;
                        default:
                            grid[r][c] = (char)(rowEnemiesCount + colEnemiesCounts[c]);
                    }
                }
                rowEnemiesCount = 0;
            }
            
            Arrays.fill(colEnemiesCounts, 0);
            int max = 0;
            for (int r = n - 1; r >= 0; r --) {
                for (int c = m - 1; c >= 0; c --) {
                    switch(grid[r][c]) {
                        case 'E':
                            rowEnemiesCount ++;
                            colEnemiesCounts[c] ++ ;
                            break;
                        case 'W':
                            rowEnemiesCount = 0;
                            colEnemiesCounts[c] = 0;
                            break;
                        default:
                            grid[r][c] += rowEnemiesCount + colEnemiesCounts[c];
                            max = Math.max(max, grid[r][c]);
                    }
                }
                rowEnemiesCount = 0;
            }
            
            return max;
        }
    }
    

Log in to reply
 

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