# Verbose Java O(m*n) Solution, HashMap

• The difficult parts are validating the two 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`

My solution:

1. Scan each row. If that row has `N` black pixels, put a string `signature`, which is concatenation of each characters in that row, as key and how many times we see that `signature` into a HashMap. Also during scan each row, we record how many black pixels in each column in an array `colCount` and will use it in step 2.
For input:
[['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'W', 'B', 'W', 'B', 'B']]
We will get a HashMap:
{"WBWBBW": 3, "WWBWBB": 1}
and colCount array:
[0, 3, 1, 3, 4, 1]
2. Go through the HashMap and if the count of one `signature` is `N`, those rows potentially contain black pixels we are looking for. Then we validate each of those columns. For each column of them has `N` black pixels (lookup in `colCount` array), we get `N` valid black pixels.
For above example, only the first `signature` "WBWBBW" has count == 3. We validate 3 column 1, 3, 4 where char == 'B', and column 1 and 3 have 3 'B', then answer is 2 * 3 = 6.

Time complexity analysis:
Because we only scan the matrix for one time, time complexity is O(m*n). m = number of rows, n = number of columns.

``````public class Solution {
public int findBlackPixel(char[][] picture, int N) {
int m = picture.length;
if (m == 0) return 0;
int n = picture[0].length;
if (n == 0) return 0;

Map<String, Integer> map = new HashMap<>();
int[] colCount = new int[n];

for (int i = 0; i < m; i++) {
String key = scanRow(picture, i, N, colCount);
if (key.length() != 0) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
}

int result = 0;
for (String key : map.keySet()) {
if (map.get(key) == N) {
for (int j = 0; j < n; j++) {
if (key.charAt(j) == 'B' && colCount[j] == N) {
result += N;
}
}
}
}

return result;
}

private String scanRow(char[][] picture, int row, int target, int[] colCount) {
int n = picture[0].length;
int rowCount = 0;
StringBuilder sb = new StringBuilder();

for (int j = 0; j < n; j++) {
if (picture[row][j] == 'B') {
rowCount++;
colCount[j]++;
}
sb.append(picture[row][j]);
}

if (rowCount == target) return sb.toString();
return "";
}
}
``````

• Same idea here unless I forget to use the HashMap part :(

• i don't know what's the meaning of rule 2

• Great work for using hashmap to store the string of rows. So that we don't need to check rule 2, which is really awesome!

Just a suggestion, since you already traversed all picture in your part 1. You could keep using the `int[] cols` to store the count for each columns. It will help us to save some time instead of using `scanCol`.

Here is my solution for your reference.

``````public int findBlackPixel(char[][] picture, int N) {
if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
int m = picture.length, n = picture[0].length;
int[] cols = new int[n];
Map<String, Integer> map = new HashMap<>();

for (int i = 0; i < m; i++) {
int count = 0;
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
if (picture[i][j] == 'B') {
cols[j]++;
count++;
}
sb.append(picture[i][j]);
}
if (count == N) {
String curRow = sb.toString();
map.put(curRow, map.getOrDefault(curRow, 0) + 1);
}
}

int res = 0;
for (String row : map.keySet()) {
if (map.get(row) != N) continue;
for (int i = 0; i < n; i++) {
if (row.charAt(i) == 'B' && cols[i] == N) {
res += N;
}
}
}
return res;
}
``````

• @Free9 You are right. Updated my post, thanks!

• at first I thought "exactly the same as row R" mentioned in rule 2 means the number of black pixels should be same.......
then I'm really confused why we should use map.get(key)==N......
I wasted half an hour......

• ``````    int m = picture.length;
if (m == 0) return 0;
int n = picture[0].length;
if (n == 0) return 0;
``````

Is it possible that `m != 0` but `n == 0` ?
`if (n == 0) return 0;` this is redundant.

• @zzhai It's totally possible. Try this:

``````int[][] a = new int[10][0];
System.out.println(a[0].length);
``````

• @shawngao

Got it. Thanks.

• if(map.get(key) == N)

Can anyone help explain why this matters? I can not interpret rule 2 to this...

For instance, in this test case if there are only two signatures are identical, is the answer still 6? or in your logic, 0?

• @awwwyellow According to the problem, our task is to:

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`

Look at the red `B` in the example in my post, it satisfy rule 1 when N = 3. To satisfy rule 2, for each B in column 1, that row (which are row 1 and 2) should be exactly the same as row 0. In this case, they are the same. So the red `B` is a `Lonely Pixel`.
[['W', '`B`', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'B', 'W', 'B', 'B', 'W'],
['W', 'W', 'B', 'W', 'B', 'B']]

Back to your question, if there are only two signatures are identical, the answer is `0`. Check the following example:
[['W', '`B`', 'W', '`B`', '`B`', 'W'],
['B', '`B`', 'W', '`B`', 'W', 'W'],
['W', '`B`', 'W', '`B`', '`B`', 'W'],
['W', 'W', 'B', 'W', '`B`', 'B']]
Those red `B` satisfy rule 1 but all failed rule 2.

• @shawngao

Thank you for the answer in detail! Really appreciate it!

Now I know that I missed a very obvious thing, that is, in rule 2

1. For all rows that have a black pixel at column C...

Since qualified column C can only have N black pixels, there should be exactly N column R. And only when they are identical, those black pixels count.

• @shawngao great solution, I've got the same here but I've optimized on the "row key" by converting the pixel string to an array of longs then to a string by concatenating the longs which should yield a much more compact row 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;
}
``````

• @Free9 in if (row.charAt(i) == 'B' && cols[i] == N)
I believe row.charAt(i) == 'B' is redundant.

• Nice solution. A small optimization - StringBuilder is not required. You can simply do -

if (rowCount == target) return new String(picture[row]);

• Here is my code, cannot be compared 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;
}
}
``````

• Beautiful solution : Was confused a bit on why there is map.get(key) == N check. Finally got it. The code map.get(key) == N ensures that there are at least N Black (B) pixels in the column C and the code cols[i] == N further ensures that there are exactly N black pixels (no other row has black pixel at that position) in column C.

• Thanks for sharing.
I have a space-cost optimization.
Actually, we don't need to store a hard-copy of a row's values, we can just store the row's reference pointer.
Here is my code:

``````class Solution {
public int findBlackPixel(char[][] picture, int N) {
if(picture==null || picture.length==0 || picture[0].length==0)
return 0;

int m=picture.length;
int n=picture[0].length;
int[] cols = new int[n];

Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
Map<Integer, char[]> rowMap = new HashMap<Integer, char[]>();
for(int i=0; i<m; i++){
int count=0; //count number of 'B' in current row
for(int j=0; j<n; j++)
if(picture[i][j]=='B'){
cols[j]++;
count++;
}

if(count==N){ //if current row has the desired number of 'B'
int hash = Arrays.hashCode( picture[i] );
countMap.put( hash, countMap.getOrDefault(hash, 0)+1 );  //put the reference of the current row, rather than the hard copy
rowMap.putIfAbsent(hash, picture[i]);
}
}

int result=0;
for(Map.Entry<Integer, Integer> entry : countMap.entrySet())
if( entry.getValue()==N ){ //if there are N rows, all of which are the same
char[] row = rowMap.get( entry.getKey() );
for(int j=0; j<n; j++)
if(row[j]=='B' && cols[j]==N) //current position is 'B', current col also has N 'B'
result += N;
}

return result;
}
}
``````

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