C# - Explained - use counting matrix O(rows x cols) time, O(rows x cols) memory


  • 0

    The idea is to allocate a new integer matrix of same dimensions as input matrix. First sum up the counts of enemies across rows (summing left/right), resetting when hitting a wall. Put the count in each cell in the counts matrix. Then do the same across columns (summing up/down), but this time add to the same counts matrix with the catch that you want to avoid double counting a particular cell. While setting the column sums in the counts matrix check that the current cell is an Enemy or not and avoid double counting if this cell is an Enemy.

    After all the counts are determined, just iterate through the counting matrix and pick the max value only considering cells that are Empty.

    Time is O(rows x cols) for iterating rows and cols and finding max, which amounts to O(rows x cols).
    Space is clearly the counting matrix which is O(rows x cols).

        public class Solution
        {
            public int MaxKilledEnemies(char[,] grid)
            {
                int rowCount = grid.GetLength(0);
                int colCount = grid.GetLength(1);
    
                int[,] enemyCounts = new int[rowCount, colCount];
                CountEnemiesForRows(grid, enemyCounts, rowCount, colCount);
                CountEnemiesForCols(grid, enemyCounts, rowCount, colCount);
    
                return FindMax(grid, enemyCounts, rowCount, colCount);
            }
    
            public int FindMax(char[,] grid, int[,] enemyCounts, int rowCount, int colCount)
            {
                int max = 0;
                for (int r = 0; r < rowCount; r++)
                {
                    for (int c = 0; c < colCount; c++)
                    {
                        // only consider Empty cells
                        if (grid[r, c] == '0')
                        {
                            max = enemyCounts[r, c] > max ? enemyCounts[r, c] : max;
                        }
                    }
                }
                return max;
            }
    
            public void CountEnemiesForRows(char[,] grid, int[,] enemyCounts, int rowCount, int colCount)
            {
                for (int r = 0; r < rowCount; r++)
                {
                    int colStart = 0;
                    int enemyCount = 0;
                    for (int c = 0; c < colCount; c++)
                    {
                        if (grid[r, c] == 'E')
                        {
                            enemyCount += 1;
                        }
    
                        if (grid[r, c] == 'W' || c == colCount - 1)
                        {
                            while (colStart <= c)
                            {
                                enemyCounts[r, colStart++] += enemyCount;
                            }
                            enemyCount = 0;
                            colStart = c + 1;
                        }
                    }
                }
            }
    
            public void CountEnemiesForCols(char[,] grid, int[,] enemyCounts, int rowCount, int colCount)
            {
                for (int c = 0; c < colCount; c++)
                {
                    int rowStart = 0;
                    int enemyCount = 0;
                    for (int r = 0; r < rowCount; r++)
                    {
                        if (grid[r, c] == 'E')
                        {
                            enemyCount += 1;
                        }
    
                        if (grid[r, c] == 'W' || r == rowCount - 1)
                        {
                            while (rowStart <= r)
                            {
                                // if this cell has an enemy -> subtract 1 to avoid double counting
                                enemyCounts[rowStart, c] += enemyCount + (grid[rowStart,c] == 'E' ? -1 : 0);
                                rowStart++;
                            }
                            enemyCount = 0;
                            rowStart = r + 1;
                        }
                    }
                }
            }
        }
    

Log in to reply
 

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