Java DP solultion, O(mn) time, O(mn) space, beats 90%


  • 1
    A

    Using only O(mn) memory for additional grid (not as perfect as (O(m) space solutions given by other users but anyway..) we can solve this problem through O(4mn) iterations. We just need to scan the grid from left to right and accumulate the sum of enemies by dp[i][j] from left since the last wall. Then we do the same from top to bottom, from right to left and finally from bottom to top. On each iteration we increase the dp[i][j] value by cumulative sum.

      public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
    
            // from left to right
            for (int i = 0; i < m; i++) {
                int current = 0;
                for (int j = 0; j < n; j++) 
                    current = process(grid, dp, i, current, j);
            }
            // from top to bottom
            for (int j = 0; j < n; j++) {
                int current = 0;
                for (int i = 0; i < m; i++) 
                    current = process(grid, dp, i, current, j);
            }
            // from right to left
            for (int i = 0; i < m; i++) {
                int current = 0;
                for (int j = n - 1; j >= 0; j--) 
                    current = process(grid, dp, i, current, j);
            }
            int ans = 0;
            // from bottom to top
            for (int j = 0; j < n; j++) {
                int current = 0;
                for (int i = m - 1; i >= 0; i--) {
                    current = process(grid, dp, i, current, j);
                    if (grid[i][j] == '0')  ans = Math.max(ans, dp[i][j]);
                }
            }
    
            return ans;
        }
    
        private int process(char[][] c, int[][] dp, int i, int current, int j) {
            if (c[i][j] == 'W') current = 0;
            if (c[i][j] == 'E') current++;
            dp[i][j] += current;
            return current;
        }
    

  • 0
    S
    This post is deleted!

  • 0
    T

    Good Solution!

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            if(grid==null||grid.length<1) return 0;
            
            int[][] count=new int[grid.length][grid[0].length];
            
            for(int i=0;i<grid.length;i++){
                int current=0;
                for(int j=0;j<grid[0].length;j++){
                     current=check(grid,count,i,j,current);
                }
            }
            
            for(int i=0;i<grid.length;i++){
                int current=0;
                for(int j=grid[0].length-1;j>=0;j--){
                    current=check(grid,count,i,j,current);
                }
            }
            
            for(int j=0;j<grid[0].length;j++){
                int current=0;
                for(int i=0;i<grid.length;i++){
                    current=check(grid,count,i,j,current);
                }
            }
            
            int max=0;
            for(int j=0;j<grid[0].length;j++){
                int current=0;
                for(int i=grid.length-1;i>=0;i--){
                    current=check(grid,count,i,j,current);
                    if(grid[i][j]=='0'){
                      max=Math.max(max,count[i][j]);  
                    }
                }
            }
            return max;
        }
        
        public int check(char[][] grid,int[][] count,int i,int j,int current){
            if(grid[i][j]=='W'){
                return 0;
            }else if(grid[i][j]=='E'){
                current++;
                return current;
            }else{//'0'
                  count[i][j]+=current;
                  return current;
            }
            
        }
    }
    

Log in to reply
 

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