Java O(4mn) solution


  • 0
    C

    There are two loops as you can seen. The first loop I update every empty place by increase the enemy on its row. The second loop I update every place by increase the enemy on its col. Every loop is 2*mn, so the final time complexity is O(4mn).

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0) return 0;
            int m = grid.length, n = grid[0].length;
            int[][] matrix = new int[m][n];
            
            for (int i = 0; i < m; i++) {
                int col = 0;
                int pre = 0;
                while (col < n) {
                    int count = 0;
    
                    while (col < n && grid[i][col] != 'W') {
                        count = grid[i][col] == 'E' ? count + 1 : count;
                        col++;
                    }
                    for (int j = pre; j < col; j++) {
                        if (grid[i][j] != 'E' && grid[i][j] != 'W') matrix[i][j] += count;
                    }
                    pre = col + 1;
                    col++;
                }
            }
            
            int max = 0;
            for (int i = 0; i < n; i++) {
                int row = 0;
                int pre = 0;
                while (row < m) {
                    int count = 0;
                    
                    while (row < m && grid[row][i] != 'W') {
                        count = grid[row][i] == 'E' ? count + 1 : count;
                        row++;
                    }
                    for (int j = pre; j < row; j++) {
                        if (grid[j][i] != 'E' && grid[j][i] != 'W') {
                            matrix[j][i] += count;
                            max = matrix[j][i] > max ? matrix[j][i] : max;
                        }
                    }
                    pre = row + 1;
                    row++;
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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