533. Lonely Pixel II π
Description
Given an m x n
picture
consisting of black 'B'
and white 'W'
pixels and an integer target, return the number of black lonely pixels.
A black lonely pixel is a character 'B'
that located at a specific position (r, c)
where:
- Row
r
and columnc
both contain exactlytarget
black pixels. - For all rows that have a black pixel at column
c
, they should be exactly the same as rowr
.
Example 1:
Input: picture = [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]], target = 3 Output: 6 Explanation: All the green 'B' are the black pixels we need (all 'B's at column 1 and 3). 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 target = 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.
Example 2:
Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1 Output: 0
Constraints:
m == picture.length
n == picture[i].length
1 <= m, n <= 200
picture[i][j]
is'W'
or'B'
.1 <= target <= min(m, n)
Solutions
Solution 1: Counting
The second condition in the problem is equivalent to requiring that for each column containing black pixels, these rows are exactly the same.
Therefore, we can use an adjacency list $g$ to store all the rows containing black pixels in each column, i.e., $g[j]$ represents the set of all rows containing black pixels in the $j$-th column. In addition, we use an array $rows$ to store the number of black pixels in each row.
Next, we traverse each column. For each column, we find the first row $i_1$ containing black pixels. If the number of black pixels in this row is not equal to $target$, then this column cannot contain lonely pixels, and we skip it directly. Otherwise, we check whether all the rows containing black pixels in this column are exactly the same as the $i_1$-th row. If so, all the black pixels in this column are lonely pixels, and we add $target$ to the answer.
After the traversal, we return the answer.
The time complexity is $O(m \times n^2)$, and the space complexity is $O(m \times n)$, where $m$ and $n$ are the number of rows and columns in the matrix respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
|