Lonely Pixel I

Medium · Arrays & Hashing · Explanation and code example

Space Optimized Counting

How it works

We can avoid using extra arrays by reusing the first row and first column of the grid itself to store the counts. However, we must first handle lonely pixels in the first row and first column separately, since those cells will be overwritten. After that, we convert the border cells to store counts and use them to check interior cells.

Steps

First, check for lonely pixels in the first row and first column using a helper function that scans the entire row and column.
Convert the first row and first column from 'B'/'W' to '0'/'1' to use as counters.
Iterate through the interior cells (excluding first row and column). For each black pixel, increment the count stored in the corresponding first row and first column cells.
Finally, scan the interior again. A black pixel at (i, j) is lonely if both picture[0][j] and picture[i][0] equal '1'.
Return the total count.

Complexity

Time complexity: O(M × N)
Space complexity: O(1) constant space

Where M is the number of rows in the given matrix picture, and N is the number of columns in it.

Things to watch for

Checking Only the Row or Only the Column

A common mistake is to count a black pixel as lonely if it is the only black pixel in its row, without also verifying that it is the only black pixel in its column (or vice versa). Both conditions must be satisfied simultaneously for a pixel to be considered lonely.

Confusing Row and Column Indices

When working with 2D matrices, it is easy to mix up row and column indices. Remember that picture[i][j] refers to row i and column j. Swapping these when updating or querying counts will produce incorrect results.

Forgetting to Handle Edge Cases with No Black Pixels

If the matrix contains no black pixels at all, the answer is 0. While most implementations handle this naturally, some solutions that assume at least one black pixel exists may encounter issues or unnecessary iterations.

Python code example

from typing import List

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        # Returns true if the cell at (x, y) is lonely.
        # There should not be any other black cell
        # In the first row and column except (x, y) itself.
        def check(x, y):
            n = len(picture)
            m = len(picture[0])

            cnt = 0
            for i in range(n):
                cnt += 1 if picture[i][y] == 'B' else 0

            for j in range(m):
                # avoid double count (x, y)
                if j != y:
                    cnt += 1 if picture[x][j] == 'B' else 0

            return picture[x][y] == 'B' and cnt == 1

        n = len(picture)
        m = len(picture[0])

        answer = 0
        for j in range(m):
            answer += 1 if check(0, j) else 0

        for i in range(1, n):
            answer += 1 if check(i, 0) else 0

        # Convert cell 'B' to '1' and 'W' to '0'
        for j in range(m):
            picture[0][j] = '1' if picture[0][j] == 'B' else '0'

        for i in range(n):
            picture[i][0] = '1' if picture[i][0] == 'B' else '0'

        # If the cell is black increment the count of corresponding row and column by 1
        for i in range(1, n):
            for j in range(1, m):
                if picture[i][j] == 'B':
                    picture[i][0] = chr(ord(picture[i][0]) + 1)
                    picture[0][j] = chr(ord(picture[0][j]) + 1)

        for i in range(1, n):
            for j in range(1, m):
                if picture[i][j] == 'B':
                    if picture[0][j] == '1' and picture[i][0] == '1':
                        answer += 1

        return answer

C++ code example

class Solution {
public:
    // Returns true if the cell at (x, y) is lonely.
    // There should not be any other black cell
    // In the first row and column except (x, y) itself.
    bool check(vector<vector<char>>& picture, int x, int y) {
        int n = int(picture.size());
        int m = int(picture[0].size());

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += (picture[i][y] == 'B');
        }

        for (int j = 0; j < m; j++) {
            // avoid double count (x, y)
            if (j != y) cnt += (picture[x][j] == 'B');
        }
        return picture[x][y] == 'B' && cnt == 1;
    }

    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = int(picture.size());
        int m = int(picture[0].size());

        int answer = 0;
        // Lonely cells in the first row
        for (int j = 0; j < m; j++) {
            answer += check(picture, 0, j);
        }
        //Lonely cells in the first column
        for (int i = 1; i < n; i++) {
            answer += check(picture, i, 0);
        }

        // Convert cell 'B' to '1' and 'W' to '0'
        for (int j = 0; j < m; j++) {
            picture[0][j] = (picture[0][j] == 'B' ? '1' : '0');
        }

        for (int i = 0; i < n; i++) {
            picture[i][0] = (picture[i][0] == 'B' ? '1' : '0');
        }

        // If the cell is black increment the count of corresponding row and column by 1
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (picture[i][j] == 'B') {
                    picture[i][0]++;
                    picture[0][j]++;
                }
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (picture[i][j] == 'B') {
                    if (picture[0][j] == '1' && picture[i][0] == '1') {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations