[Java] [C++] Clean Code with Explanation - map<int, set<int>>


  • 4

    Analysis

    /**
     * Steps:
     * >> 1. create map<int, set<int>> cols, rows; -- to store black dots on that row;
     * 
     *     _0_1_2_3_4_5_
     *  0 | 0 l 0 1 1 0     rows[0] = {1, 3, 4}
     *  1 | 0 l 0 1 1 0     rows[1] = {1, 3, 4}
     *  2 | 0 l 0 1 1 0     rows[2] = {1, 3, 4}
     *  3 | 0 0 1 0 1 0     rows[3] = {  2,  4}
     * 
     * >> 2. for every pixel meet rule 1, that is: pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N
     *       check rule2: for every row k in cols[j];  check that row[k] = row[i];
     * 
     * We can tell the 6 black pixel in col 1 and col 3 are lonely pixels
     *     _0_1_2_3_4_5_
     *  0 | 0 L 0 L 1 0     rows[0] = {1, 3, 4}  =
     *  1 | 0 L 0 L 1 0     rows[1] = {1, 3, 4}  =
     *  2 | 0 L 0 L 1 0     rows[2] = {1, 3, 4} 
     *  3 | 0 0 1 0 1 0     rows[3] = {  2,  4}
     *
     */
    

    C++

    class Solution {
    public:
        int findBlackPixel(vector<vector<char>>& pic, int N) {
            int m = pic.size();
            int n = pic[0].size();
            unordered_map<int, set<int>> rows;  // black pixels in each row
            unordered_map<int, set<int>> cols;  // black pixels in each col
            /* 1. create map<int, set<int>> cols, rows; -- to store black dots on that row; */
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (pic[i][j] == 'B') {
                        rows[i].insert(j);
                        cols[j].insert(i);
                    }
                }
            }
            /* 2. for every pixel meet rule 1: pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N */
            int lonelys = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n && rows.count(i); j++) {
                    if (pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N) {   // rule 1 fulfilled
                        /* check rule2: for every row k in cols[j];  check that row[k] = row[i]; */
                        bool lonely = true;
                        for (int r : cols[j]) {
                            if (rows[r] != rows[i]) {
                                lonely = false; break;
                            }
                        }
                        lonelys += lonely;
                    }
                }
            }
            return lonelys;
        }
    };
    

    Java

    public class Solution {
        public int findBlackPixel(char[][] pic, int N) {
            int m = pic.length;
            int n = pic[0].length;
            Map<Integer, Set<Integer>> rows = new HashMap<Integer, Set<Integer>>(); // black pixels in each row;
            Map<Integer, Set<Integer>> cols = new HashMap<Integer, Set<Integer>>(); // black pixels in each col;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (pic[i][j] == 'B') {
                        if (!rows.containsKey(i)) { rows.put(i, new HashSet<Integer>()); }
                        if (!cols.containsKey(j)) { cols.put(j, new HashSet<Integer>()); }
                        rows.get(i).add(j);
                        cols.get(j).add(i);
                    }
                }
            }
            int lonelys = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n && rows.containsKey(i); j++) {
                    if (pic[i][j] == 'B' && rows.get(i).size() == N && cols.containsKey(j) && cols.get(j).size() == N) {   // rule 1 fulfilled
                        int lonely = 1;
                        for (int row : cols.get(j)) {
                            if (!rows.get(i).equals(rows.get(row))) {
                                lonely = 0; break;
                            }
                        }
                        lonelys += lonely;
                    }
                }
            }
            return lonelys;
        }
    }
    

  • 0

    This is a nice clean solution however I believe you have some in-efficiency here in this block (Java code)

    for (int row : cols.get(j)) {
        if (!rows.get(i).equals(rows.get(row))) {                                      
            lonely = 0; break;
        }
    }
    

    note that Set.equals() is an O(size of set) operation.
    https://docs.oracle.com/javase/7/docs/api/java/util/AbstractSet.html#equals(java.lang.Object)

    you are comparing each row to every candidate row by checking potentially all cells in the row (if the row contained all 'B' for example). If, for example, rows 1, 2, 3, 4 were all equal and each had 10 B's. On row 1, B 1 you would check for row equality against 1, 2, 3, 4. Then row 1 B 2 you'd do the same and again for each B in the row. Then again for rows 2, 3, 4, each time checking against rows 1, 2, 3, 4. This is repeating comparisons that you have already done.

    This is where the "row key" approach has the advantage. Compute a "row key" which uniquely identifies the row and you need only keep a count of the frequency of each row key. From there you can massively reduce the number of redundant checking needed. Here is my row key solution.

        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;
        }
    

  • 0

    @jdrogin Hey! Very good point on Set.equals() times O(size of set)!
    But it is still O(n), and I do believe all Set.equals() implementation should return false if 2 set have different size.
    While converting them to a string takes time O(size of set) any ways and there is no best case.
    Plus, I have no idea how C# string append operates, but Java string is immutable, you have to append in to an StringBuilder then convert to a String which take even more time I guess :(

    But you are right, once you have the key assembled, it is probably more efficient than set comparison. :)


  • 0
    F

    Here is my code, very similar to yours.

    public class Solution {
        public int findBlackPixel(char[][] picture, int N) {
            int count = 0, R = picture.length, C = picture[0].length;
            int[] row = new int[R];
            int[] col = new int[C];
            HashMap<Integer,String> map = new HashMap<>();
            for(int i = 0;i<R;i++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0;j<C;j++){
                    sb.append(picture[i][j]);
                    if(picture[i][j] == 'B'){
                        row[i]++;
                        col[j]++;
                    }
                }
                map.put(i,sb.toString());
            }
            for(int i = 0;i<R;i++){
                for(int j = 0;j<C;j++){
                    if(picture[i][j] == 'B'){
                        if(row[i] == N && col[j] == N){
                            int n = 0;
                            for(int k = 0;k<R && n < N;k++){
                                if(picture[k][j] == 'B'){
                                    if(!map.get(i).equals(map.get(k))) break;
                                    n++;
                                }
                            }
                            if(n == N) count++;
                        }
                    }
                }
            }
            return count;
        }
    }
    

Log in to reply
 

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