533. Lonely Pixel II

Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:

  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

The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

Example:

Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']] 

N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

  1. The range of width and height of the input 2D array is [1,200].

Rust Solution

struct Solution;

impl Solution {
    fn find_black_pixel(picture: Vec<Vec<char>>, n: i32) -> i32 {
        let k = n as usize;
        let n = picture.len();
        let m = picture[0].len();
        let mut rows: Vec<Vec<usize>> = vec![vec![]; n];
        let mut cols: Vec<Vec<usize>> = vec![vec![]; m];
        for i in 0..n {
            for j in 0..m {
                if picture[i][j] == 'B' {
                    rows[i].push(j);
                    cols[j].push(i);
                }
            }
        }
        let mut res = 0;
        for i in 0..n {
            for j in 0..m {
                if picture[i][j] == 'B' && rows[i].len() == k && cols[j].len() == k {
                    if cols[j].iter().all(|&r| rows[r] == rows[i]) {
                        res += 1;
                    }
                }
            }
        }
        res
    }
}

#[test]
fn test() {
    let picture = vec_vec_char![
        ['W', 'B', 'W', 'B', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'B', 'W'],
        ['W', 'B', 'W', 'B', 'B', 'W'],
        ['W', 'W', 'B', 'W', 'B', 'W']
    ];
    let n = 3;
    let res = 6;
    assert_eq!(Solution::find_black_pixel(picture, n), res);
}

Having problems with this solution? Click here to submit an issue on github.