# Java O(nm) time with O(n+m) Space and O(1) Space Solutions

• O(nm) Time, O(n+m) Space Solution:

``````public int findLonelyPixel(char[][] picture) {
int n = picture.length, m = picture[0].length;

int[] rowCount = new int[n], colCount = new int[m];
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B') { rowCount[i]++; colCount[j]++; }

int count = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) count++;

return count;
}
``````

O(nm) Time, O(1) Space Solution:

``````public int findLonelyPixel(char[][] picture) {
int n = picture.length, m = picture[0].length;

int firstRowCount = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] == 'B') {
if (picture[0][j] < 'Y' && picture[0][j] != 'V') picture[0][j]++;
if (i == 0) firstRowCount++;
else if (picture[i][0] < 'Y' && picture[i][0] != 'V') picture[i][0]++;
}

int count = 0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (picture[i][j] < 'W' && (picture[0][j] == 'C' || picture[0][j] == 'X')) {
if (i == 0) count += firstRowCount == 1 ? 1 : 0;
else if (picture[i][0] == 'C' || picture[i][0] == 'X') count++;
}

return count;
}
``````

• Nice and clean code. But for the O(1) solution, there is a corner case where there are exactly 22 B's in one row, in which the first column will become 'X'.

Here's the input:
`["WWWWWWWWWWWWWWWWWWWWWWWWW","BWBBBBBBBBBBBBBBBBBBBBBWW"]`

Expected: 0

• @kaiwen789 Hey, thanks for pointing this corner case out! I have updated solution accordingly.

• @compton_scatter Nice work!

• Great O(1) solution. I think this question is very similar to set matrix zeros

• Why we use 'Y', 'V', 'C', anyone knows? Thanks!

• @SuperHero007

The hack here is to mutate the first row and first column of the given matrix to store the counts of items in the row/column.

`W + 1 = X` --> one item in the row/column
`B + 1 = C` --> one item in the row/column, and the first row is the black pixel
`W + 2 = Y` --> two items in the row/column
`W - 1 = V` --> this prevents wrap-around past W if there are more than 255 black pixels in a row/column

• The same idea as "Design Tic-Tac-Toe".

• how to solve this problem with DFS?

• @JagdishHiremath I have the same idea as you: how to use DFS. But my code is very ugly. Some suggestion please, thx.

``````public int findLonelyPixel(char[][] picture) {
int numLone = 0;
for (int row = 0; row < picture.length; row++) {
for (int col = 0; col < picture[row].length; col++) {
if (picture[row][col] == 'W') {
continue;
}
if (dfs(picture, row - 1, col, new int[] {-1, 0}) && dfs(picture, row + 1, col, new int[] {1, 0})
&& dfs(picture, row, col - 1, new int[] {0, -1}) && dfs(picture, row, col + 1, new int[] {0, 1})) {
numLone++;
}
}
}
return numLone;
}

// use dfs to find if current pixel is lonely
private boolean dfs(char[][] picture, int row, int col, int[] increase) {
// base case
if (row < 0 || row >= picture.length || col < 0 || col >= picture[0].length) {
return true;
} else if (picture[row][col] == 'B') {
return false;
}
// recursion
return dfs(picture, row + increase[0], col + increase[1], increase);
}
``````

''

• This post is deleted!

• Here is my one pass code, using hashmap. The idea is the same

``````    public int findLonelyPixel(char[][] picture) {
HashMap<Integer,Integer> row2Cnt = new HashMap<>();
HashMap<Integer,Integer> col2Cnt = new HashMap<>();
int cnt = 0;

for (int row = 0; row < picture.length; row++) {
for (int col = 0; col < picture[0].length; col++) {
if (picture[row][col] == 'W')
continue;

int rowCnt = row2Cnt.getOrDefault(row,0);
int colCnt = row2Cnt.getOrDefault(row,0);

if (rowCnt == 0 && colCnt == 0) {
cnt++;
}

else {
if (rowCnt == 1)
cnt--;
if (colCnt == 1)
cnt--;
}

row2Cnt.put(row,rowCnt + 1);
col2Cnt.put(col,colCnt + 1);
}
}

return cnt;
}

``````

• @compton_scatter You only need to return the
Math.min(countRow1, countCol1).
countRow1 = the number of 1's in rowCount array
countCol1 = the number of 1's in colCount array

In this step, it has O(m + n) time rather than another O(nm) to loop through the entire picture array.

• @Avidiax Thinking maybe 'D' is enough to judge, instead of 'V'

• Add some conditions to avoid unnecessary check.

``````class Solution {
public int findLonelyPixel(char[][] picture) {
int m = picture.length, n = picture[0].length;
int[] row = new int[m];
int[] col = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (picture[i][j] == 'B') {
row[i]++;
col[j]++;
}
}
}
int res = 0;
for (int i = 0; i < m; i++) {
// Only if the current row has only 1 black, we will step into it.
if (row[i] != 1) {
continue;
}
for (int j = 0; j < n; j++) {
// Since this row only has 1 black, after we met it, we can break and search next row.
if (picture[i][j] == 'B') {
if (col[j] == 1) {
res++;
}
break;
}
}
}
return res;
}
}
``````

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