Easy to understand Java solution 28ms using hashmap


  • 0
    Q

    As we can see from the question, we have two rules to follow:

    1. Row R and column C both contain exactly N black pixels.

    2. For all rows that have a black pixel at column C, they should be exactly the same as row R

    We can use two arrays to remember how many B in each rows and cols. In my solution, I use rs[] and cs[].
    In the meantime, I can remember how may different rows in my array. I use the hashmap to remember that. Key is the rows, a value is how many times.

    After we init the hashmap. Everything becomes simple. We can do another pass.

    After we find a 'B', which rows and cols have the same Bs equal to N, which means it satisfied the first rules. We can get how many times this kind of rows appear. If it appears N times, that means it satisfied the second rows. So this B is what we need.

    public int findBlackPixel(char[][] picture, int N) {
    		if (picture.length == 0)
    			return 0;
    		int rows = picture.length;
    		HashMap<String, List<Integer>> map = new HashMap<>();
    		int cols = picture[0].length;
    		int[] rs = new int[rows];
    		int[] cs = new int[cols];
    		int rv = 0;
    		for (int i = 0; i < rows; i++) {
    			for (int j = 0; j < cols; j++) {
    				if (picture[i][j] == 'B') {
    					rs[i]++;
    					cs[j]++;
    				}
    			}
    			String str = new String(picture[i]);
    			List<Integer> list = new ArrayList<>();
    			if (map.containsKey(str))
    				list = map.get(str);
    			list.add(i);
    			map.put(str, list);
    
    		}
    		for (int i = 0; i < rows; i++) {
    			for (int j = 0; j < cols; j++) {
    				if (picture[i][j] == 'B' && rs[i] == cs[j] && rs[i] == N) {
    					ArrayList<Integer> list = (ArrayList<Integer>) map.get(new String(picture[i]));
    					if (list.size() != cs[j])
    						break;
    					rv++;
    				}
    			}
    		}
    		return rv;
    
    	}
    

Log in to reply
 

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