531. Lonely Pixel I

MediumArrayHash TableMatrix
Leetcode Link

Problem Description

The given problem presents a two-dimensional grid called picture, represented as an m x n matrix consisting of two types of pixels - black represented by 'B' and white represented by 'W'. The task is to calculate the number of black pixels that are "lonely", which means they do not share their row or column with any other black pixels.

Intuition

The solution involves two main steps.

Firstly, we need to find the count of black pixels in every row and every column. To accomplish this, we create two arrays: one called rows for storing the counts of black pixels in each row, and one called cols for storing the counts in each column. We iterate through every element in the picture matrix; if we encounter a black pixel ('B'), we increment the corresponding elements in rows and cols.

Once we have the counts, we check for lonely pixels. We scan through our rows array to find rows that contain exactly one black pixel. For each of these rows, we loop through the columns. If we find that the black pixel in this row also resides in a column with only one black pixel, then it is a lonely black pixel. We increment our result counter (res) in this case.

By breaking down the problem into counting and then verifying against those counts, we can identify lonely pixels without checking the entire grid every single time we find a black pixel. This approach significantly optimizes our solution.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The proposed solution algorithm employs a straightforward but effective two-pass method with additional space to keep track of counts. The data structures used are two auxiliary arrays (rows and cols) to record the number of black pixels in each row and column, respectively.

First Pass: Counting Black Pixels

In the first pass, we iterate over every cell in the picture matrix using a nested loop, where the outer loop runs through the rows, and the inner loop runs through the columns. When we come across a black pixel (denoted by 'B'), we increment the count for the current row in rows[i] and the current column in cols[j]. This way, each index in the rows array will hold the number of black pixels in the corresponding row of the picture, and similarly for the cols array regarding the columns.

Initialize Count Arrays

1rows, cols = [0] * m, [0] * n

Counting Black Pixels

1for i in range(m):
2    for j in range(n):
3        if picture[i][j] == 'B':
4            rows[i] += 1
5            cols[j] += 1

Second Pass: Identifying Lonely Pixels

In the second pass, we are looking for rows that contain a single black pixel, which can be checked efficiently thanks to the rows array. For each row with a single black pixel, we examine each of its columns using another loop. If we find that a black pixel in the row also has a corresponding cols count of 1, we have found a lonely black pixel and increment our result count res. A key optimization here is that once we find the lonely black pixel in a row, we break the inner loop since there can’t be more than one lonely black pixel in a single row.

Checking Lonely Pixels and Counting

1res = 0
2for i in range(m):
3    if rows[i] == 1:
4        for j in range(n):
5            if picture[i][j] == 'B' and cols[j] == 1:
6                res += 1
7                break

Returning the Result

Finally, after both passes are completed, we return the result res, which holds the number of lonely black pixels discovered in the picture.

This algorithm effectively reduces the time complexity by ensuring that each element in the picture is visited only a fixed number of times, avoiding repeated scans of entire rows or columns. The first pass runs in O(m * n), and the second pass will, in the worst case, also run in O(m * n), making the overall time complexity O(m * n). The additional space used for the rows and cols arrays is O(m + n), which is acceptable given that it leads to a more time-efficient solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's assume we have the following 3 x 3 grid representing our picture:

1[['W', 'B', 'W'],
2 ['W', 'W', 'W'],
3 ['B', 'W', 'B']]

In this grid, 'W' represents white pixels and 'B' represents black pixels. We will refer to rows and columns starting from index 0.

First Pass: Count Black Pixels

First, we initialize our rows and cols arrays to record the black pixel counts. Since our picture is 3 x 3, both arrays will have three elements initially set to 0.

1rows = [0, 0, 0]
2cols = [0, 0, 0]

As we iterate through the picture, whenever we see a 'B', we increment the corresponding rows and cols counts.

After the first pass, our count arrays will look like this:

1rows = [1, 0, 2] // There's 1 black pixel in the first row, none in the second, and 2 in the third.
2cols = [1, 0, 1] // Likewise, there's 1 black pixel in the first and third columns, and none in the second.

Second Pass: Identifying Lonely Pixels

Next, we check for rows with a single black pixel. In our case, the first row (rows[0] == 1) contains exactly one black pixel. Now let’s check if it's a lonely pixel.

We check the column where that pixel resides; it's at picture[0][1], which is in column 1. The count in cols[1] is 0 since there are no other black pixels in that column, indicating this pixel is not lonely. Therefore, we do not increment res.

Moving on to the third row, rows[2] == 2. This row contains two black pixels, so they cannot be lonely by definition, and we skip checking the columns for this row.

Finally, we finish our scan, with res remaining at 0, indicating there are no lonely black pixels in this particular picture.

The algorithm completes and returns the result res which, for this example, is 0.

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the minimum element can be found in:

Python Solution

1from typing import List
2
3class Solution:
4    def findLonelyPixel(self, picture: List[List[str]]) -> int:
5        # Get the dimensions of the picture
6        num_rows, num_cols = len(picture), len(picture[0])
7      
8        # Initialize the arrays to track the count of black pixels in each row and column
9        row_black_counts = [0] * num_rows 
10        col_black_counts = [0] * num_cols 
11      
12        # Count the number of black pixels in each row and column
13        for i in range(num_rows):
14            for j in range(num_cols):
15                if picture[i][j] == 'B':
16                    row_black_counts[i] += 1
17                    col_black_counts[j] += 1
18      
19        # Initialize the result to count lonely pixels
20        lonely_pixel_count = 0
21      
22        # Iterate over each row of the picture
23        for i in range(num_rows):
24            # Proceed only if the row contains exactly one black pixel
25            if row_black_counts[i] == 1:
26                # Look for the lonely black pixel in the row
27                for j in range(num_cols):
28                    # Check if the current pixel is black and also the only one in its column
29                    if picture[i][j] == 'B' and col_black_counts[j] == 1:
30                        # Increment the count of lonely pixels and break as there will be no more in this row
31                        lonely_pixel_count += 1
32                        break
33      
34        # Return the count of lonely black pixels in the picture
35        return lonely_pixel_count
36

Java Solution

1class Solution {
2
3    /**
4     * Finds the number of lonely pixels (i.e. 'B's) in the picture array.
5     * A lonely pixel is defined as a 'B' that is the only one in its row and column.
6     *
7     * @param picture A 2D character array representing the picture.
8     * @return The number of lonely pixels.
9     */
10    public int findLonelyPixel(char[][] picture) {
11        // Get dimensions of the picture array.
12        int rowsCount = picture.length;
13        int colsCount = picture[0].length;
14      
15        // Initialize arrays to count the number of 'B's in each row and column.
16        int[] rowCount = new int[rowsCount];
17        int[] colCount = new int[colsCount];
18      
19        // Iterate over the picture to count how many 'B's are in each row and column.
20        for (int i = 0; i < rowsCount; ++i) {
21            for (int j = 0; j < colsCount; ++j) {
22                if (picture[i][j] == 'B') {
23                    rowCount[i]++;
24                    colCount[j]++;
25                }
26            }
27        }
28      
29        // Initialize the result variable to store the count of lonely pixels.
30        int lonelyPixelsCount = 0;
31      
32        // Iterate over the row count array to find rows with exactly one 'B'.
33        for (int i = 0; i < rowsCount; ++i) {
34            if (rowCount[i] == 1) {
35                // If a row has exactly one 'B', check columns for a lonely 'B'.
36                for (int j = 0; j < colsCount; ++j) {
37                    // Confirm that the 'B' is lonely (i.e., it's the only one in its row and column).
38                    if (picture[i][j] == 'B' && colCount[j] == 1) {
39                        lonelyPixelsCount++;
40                      
41                        // Break since we found the lonely 'B' for this row, no need to check further.
42                        break;
43                    }
44                }
45            }
46        }
47      
48        // Return the total count of lonely pixels found.
49        return lonelyPixelsCount;
50    }
51}
52

C++ Solution

1class Solution {
2public:
3    // Finds the total count of lonely pixels ('B') in a grid.
4    // A 'lonely' pixel is defined as a 'B' that is the only one in its row and column.
5    int findLonelyPixel(vector<vector<char>>& picture) {
6        int rowCount = picture.size();
7        int colCount = picture[0].size();
8        vector<int> rowCounts(rowCount, 0); // Stores counts of 'B's in each row
9        vector<int> colCounts(colCount, 0); // Stores counts of 'B's in each column
10
11        // First pass to calculate the row and column counts
12        for (int i = 0; i < rowCount; ++i) {
13            for (int j = 0; j < colCount; ++j) {
14                if (picture[i][j] == 'B') {
15                    ++rowCounts[i];
16                    ++colCounts[j];
17                }
18            }
19        }
20
21        int lonelyPixels = 0; // Will hold the total count of lonely pixels
22
23        // Second pass to identify lonely pixels
24        for (int i = 0; i < rowCount; ++i) {
25            // We only proceed if a row has a single 'B'
26            if (rowCounts[i] == 1) {
27                for (int j = 0; j < colCount; ++j) {
28                    // Check if the current 'B' is lonely, that is, it is the only one its column as well
29                    if (picture[i][j] == 'B' && colCounts[j] == 1) {
30                        ++lonelyPixels;
31                        break; // Break because we found the lonely pixel for this row
32                    }
33                }
34            }
35        }
36      
37        return lonelyPixels;
38    }
39};
40

Typescript Solution

1// Stores the count of lonely pixels in a two-dimensional character grid.
2// A lonely pixel is defined as one that is the only 'B' in both its row and column.
3
4// Function to find the total count of lonely pixels ('B') in a grid.
5function findLonelyPixel(picture: char[][]): number {
6    let rowCount = picture.length; // Number of rows in the grid
7    let colCount = picture[0].length; // Number of columns in the grid
8    let rowCounts: number[] = new Array(rowCount).fill(0); // Array to store the count of 'B's in each row
9    let colCounts: number[] = new Array(colCount).fill(0); // Array to store the count of 'B's in each column
10
11    // First pass to calculate the 'B' count for each row and column
12    for (let i = 0; i < rowCount; ++i) {
13        for (let j = 0; j < colCount; ++j) {
14            if (picture[i][j] === 'B') {
15                rowCounts[i]++;
16                colCounts[j]++;
17            }
18        }
19    }
20
21    let lonelyPixels = 0; // Initialize count of lonely pixels
22
23    // Second pass to identify and count lonely pixels
24    for (let i = 0; i < rowCount; ++i) {
25        // Skip rows that do not contain exactly one 'B'
26        if (rowCounts[i] === 1) {
27            for (let j = 0; j < colCount; ++j) {
28                // A 'B' is lonely if it's the only one in its column
29                if (picture[i][j] === 'B' && colCounts[j] === 1) {
30                    lonelyPixels++; // Increment the count of lonely pixels
31                    break; // Move to the next row since we found a lonely pixel
32                }
33            }
34        }
35    }
36
37    // Return the final count of lonely pixels
38    return lonelyPixels;
39}
40
Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Time and Space Complexity

Time Complexity

The time complexity of the code can be determined by analyzing the two nested loops that iterate through the m x n grid of the picture.

  • The first pair of nested loops goes through each cell of the picture to count the number of 'B' in each row and column. This part of the code has a complexity of O(m * n), as it needs to visit each cell exactly once.

  • The second pair of nested loops goes through each row and, if it finds a row with exactly one 'B', it then iterates through the columns of that row to find a column with exactly one 'B'. In the worst case, this might seem like another O(m * n) operation. However, the inner loop breaks as soon as it finds the lonely 'B', and because there can be at most min(m, n) lonely pixels (since each requires a unique row and a unique column), the total time for this set of loops is also bounded by O(m * n).

Thus, when adding both parts, the overall time complexity remains O(m * n) because the two parts are not nested within one another but are sequential.

Space Complexity

The space complexity of the code is derived from the extra space used to store the rows and cols counts.

  • The rows array uses O(m) space, and the cols array uses O(n) space.

Since no other significant space is used by the algorithm, the total space complexity is O(m + n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫