533

533. Lonely Pixel II (Medium)

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 column c both contain exactly target black pixels.
• For all rows that have a black pixel at column c, they should be exactly the same as row r.

 

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)

Companies: Google

Related Topics:
Array, Hash Table, Matrix

Similar Questions:

• Lonely Pixel I (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/lonely-pixel-ii
// Author: github.com/lzl124631x
// Time: O(M^2 * N)
// Space: O(MN)
class Solution {
public:
    int findBlackPixel(vector<vector<char>>& A, int target) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<vector<bool>> same(M, vector<bool>(M));
        vector<int> row(M), col(N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 'W') continue;
                row[i]++;
                col[j]++;
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = i + 1; j < M; ++j) {
                int k = 0;
                for (; k < N; ++k) {
                    if (A[i][k] != A[j][k]) break;
                }
                same[i][j] = same[j][i] = k == N;
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 'W' || row[i] != target || col[j] != target) continue;
                int k = 0;
                for (; k < M; ++k) {
                    if (k == i || A[k][j] == 'W') continue;
                    if (!same[i][k]) break;
                }
                ans += k == M;
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/lonely-pixel-ii
// Author: github.com/lzl124631x
// Time: O(M * N^2)
// Space: O(MN)
class Solution {
public:
    int findBlackPixel(vector<vector<char>>& A, int target) {
        int M = A.size(), N = A[0].size(), ans = 0;
        vector<string> B;
        for (auto &r : A) B.emplace_back(begin(r), end(r));
        vector<int> row(M), col(N);
        unordered_map<string, int> m;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (B[i][j] == 'W') continue;
                ++row[i];
                ++col[j];
            }
            ++m[B[i]];
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (B[i][j] == 'W' || row[i] != target || col[j] != target || m[B[i]] != target) continue;
                ++ans;
            }
        }
        return ans;
    }
};