C# - row keys using bit to long array for efficient hashing


  • 0

    The solution to this problem is to pre-count the 'B' in each column and row but also to somehow compare rows. What comes to mind is we need a key to represent each row and as long as we know that there are x rows with the same key we can solve this problem by checking each 'B' has a row count, column count and row key count all equal to N.

    The difficultly really comes down to how to efficiently form the row keys. We could simply use a string and build the string out of all the characters in a row. But we can do much better if we look at each pixel as zero or one then realize this can be "serialized" as an integer (or long in this case) array. Then we can finally form the row key from the array of longs which will be much more compact than just serializing each pixel into our string key.

    
        public int FindBlackPixel(char[,] picture, int N) 
        {
            int n = picture.GetLength(0);
            int m = picture.GetLength(1);
            int[] rowCnts = new int[n];
            int[] colCnts = new int[m];
            string[] rowKeys = new string[n];
            Dictionary<string, int> rowKeyMap = new Dictionary<string,int>();
            
            for (int i = 0; i < n; i++)
            {
                long[] keyArr = new long[(m+63)/64];
                for (int j = 0; j < m; j++)
                {
                    if (picture[i,j] == 'B')
                    {
                        rowCnts[i]++;
                        colCnts[j]++;
                        keyArr[j/64] |= (long)1 << (j % 64); 
                    }
                }
                
                string key = "";
                foreach (long x in keyArr) key+= x.ToString() + ",";
                
                rowKeys[i] = key;
                if (!rowKeyMap.ContainsKey(key)) rowKeyMap[key] = 0;
                rowKeyMap[key]++;
            }
            
            int lonelyCnt = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (picture[i,j] == 'B' && rowCnts[i] == N && colCnts[j] == N && rowKeyMap[rowKeys[i]] == N)
                    {
                        lonelyCnt++;
                    }
                }
            }
            
            return lonelyCnt;
        }
    

Log in to reply
 

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