Skip to content

533. Lonely Pixel II 👎

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
class Solution {
 public:
  int findBlackPixel(vector<vector<char>>& picture, int target) {
    const int m = picture.size();
    const int n = picture[0].size();
    int ans = 0;
    vector<int> rows(m);
    vector<int> cols(n);
    vector<string> rowStrings(m);
    unordered_map<string, int> countRowStrings;

    for (int i = 0; i < m; ++i) {
      string s;
      for (int j = 0; j < n; ++j) {
        if (picture[i][j] == 'B') {
          ++rows[i];
          ++cols[j];
        }
        s += picture[i][j];
      }
      rowStrings[i] = s;
      ++countRowStrings[s];
    }

    for (int i = 0; i < m; ++i)
      if (rows[i] == target && countRowStrings[rowStrings[i]] == target)
        for (int j = 0; j < n; ++j)
          if (picture[i][j] == 'B' && cols[j] == target)
            ++ans;

    return ans;
  }
};

 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
class Solution {
  public int findBlackPixel(char[][] picture, int target) {
    final int m = picture.length;
    final int n = picture[0].length;
    int ans = 0;
    int[] rows = new int[m];
    int[] cols = new int[n];
    String[] rowStrings = new String[m];
    Map<String, Integer> countRowStrings = new HashMap<>();

    for (int i = 0; i < m; ++i) {
      StringBuilder sb = new StringBuilder();
      for (int j = 0; j < n; ++j) {
        if (picture[i][j] == 'B') {
          ++rows[i];
          ++cols[j];
        }
        sb.append(picture[i][j]);
      }
      rowStrings[i] = sb.toString();
      countRowStrings.merge(rowStrings[i], 1, Integer::sum);
    }

    for (int i = 0; i < m; ++i)
      if (rows[i] == target && countRowStrings.get(rowStrings[i]) == target)
        for (int j = 0; j < n; ++j)
          if (picture[i][j] == 'B' && cols[j] == target)
            ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def findBlackPixel(self, picture: list[list[str]], target: int) -> int:
    m = len(picture)
    n = len(picture[0])
    ans = 0
    rows = [row.count('B') for row in picture]
    cols = [col.count('B') for col in zip(*picture)]
    rowStrings = [''.join(row) for row in picture]
    countRowStrings = collections.Counter(rowStrings)

    for i, (row, stringRow) in enumerate(zip(rows, rowStrings)):
      if row == target and countRowStrings[stringRow] == target:
        for j, col in enumerate(cols):
          if picture[i][j] == 'B' and col == target:
            ans += 1

    return ans