C# - true single pass O(n) time O(row count + col count) memory


  • 1

    The idea is to keep track of if you have seen a 'B' in a row or column. I use 2 maps for this, one for rows and one for columns. The maps need to keep track of 2 things, both maps need to track the count of times they have seen a 'B' and the row map needs to track the column coordinate of the first encountered 'B' and likewise the column map needs to track the row coordinate for the first encountered 'B'.

    Here's how this works. Iterate rows and columns, when you see a 'B' increment the counts in the row and column maps. If both of these counters are 1 you count this lonely B. But, then later you come across a 'B' and one of the maps shows you now have 2 B's this row or column. Don't count this B but also you have to "uncount" the first B. Let's say it is in the same row. Here you need to be careful to signal to the column map that you have already "uncounted" this B so you don't later uncount it again. To do this you get the column index stored in your row map and increment the column map. Once the counters are past 2 they will not uncount again.

        public int FindLonelyPixel(char[,] picture) {
            Dictionary<int, int[]> rowMap = new Dictionary<int, int[]>();
            Dictionary<int, int[]> colMap = new Dictionary<int, int[]>();
            int cnt = 0;
            for (int i = 0; i < picture.GetLength(0); i++)
            {
                for (int j = 0; j < picture.GetLength(1); j++)
                {
                    if (picture[i,j] == 'B')
                    {
                        if (!rowMap.ContainsKey(i)) rowMap[i] = new int[] { j, 0 };
                        if (!colMap.ContainsKey(j)) colMap[j] = new int[] { i, 0 };
                        
                        rowMap[i][1]++;
                        colMap[j][1]++;
                        
                        if (rowMap[i][1] == 1 && colMap[j][1] == 1) 
                        {
                            cnt++;
                        }
                        else if (rowMap[i][1] == 2 && colMap[rowMap[i][0]][1] == 1)
                        {
                            cnt--;
                            colMap[rowMap[i][0]][1]++;
                        }
                        else if (colMap[j][1] == 2 && rowMap[colMap[j][0]][1] == 1)
                        {
                            cnt--;
                            rowMap[colMap[j][0]][1]++;
                        }
                        else
                        {
                            rowMap[i][1]++;
                            colMap[j][1]++;
                        }
                    }
                }
            }
            
            return cnt;
        }
    

Log in to reply
 

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