Jobs

Interviews

Discussions

Lonely Pixel I

Medium

Asked by:

18 views

Topics:

Arrays

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number of lonely pixels.

A lonely pixel is a black 'B' pixel that satisfies these conditions:

The same row contains only one black pixel.
The same column contains only one black pixel.

Example 1:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]Output: 3Explanation: All the three 'B's are lonely pixels.

Example 2:

Input: picture = [["B","B","B"],["B","B","W"],["B","B","B"]]Output: 0

Constraints:

m == picture.length
n == picture[i].length
1 <= m, n <= 500
picture[i][j] is 'W' or 'B'.

Try coding it in LeetCode

Lonely Pixel I

Medium

Asked by:

18 views

Topics:

Arrays

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number of lonely pixels.

A lonely pixel is a black 'B' pixel that satisfies these conditions:

The same row contains only one black pixel.
The same column contains only one black pixel.

Example 1:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]Output: 3Explanation: All the three 'B's are lonely pixels.

Example 2:

Input: picture = [["B","B","B"],["B","B","W"],["B","B","B"]]Output: 0

Constraints:

m == picture.length
n == picture[i].length
1 <= m, n <= 500
picture[i][j] is 'W' or 'B'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the image (number of rows and columns), and what are the maximum possible values for these dimensions?
Are the pixel values guaranteed to be only 'W' and 'B', or could there be other characters?
If there are no lonely pixels, what should the function return?
Is it possible for the input image to be null or empty?
By 'same row and column', do you mean there can only be *one* 'B' pixel in the entire row and column, or is it okay if there are zero 'B' pixels (i.e., the row or column is all 'W')?

Brute Force Solution

Approach

We need to find unique bright pixels in a picture. The brute force method involves examining each bright pixel and comparing it with every other pixel in its row and column to see if it's truly unique.

Here's how the algorithm would work step-by-step:

Go through each pixel in the picture, one at a time.
If a pixel is bright, check all other pixels in the same row.
If you find another bright pixel in the same row, the original pixel is not lonely, so move on.
If you don't find any other bright pixels in the same row, then check all other pixels in the same column.
If you find another bright pixel in the same column, the original pixel is not lonely, so move on.
If you don't find any other bright pixels in the same column, the original pixel is lonely.
Keep a count of all the lonely pixels you find.

Code Implementation

def lonely_pixel_i_brute_force(picture):
    number_of_rows = len(picture)
    number_of_cols = len(picture[0]) if number_of_rows > 0 else 0
    lonely_pixel_count = 0

    for row_index in range(number_of_rows):
        for col_index in range(number_of_cols):
            if picture[row_index][col_index] == 'B':
                is_lonely = True
                # Check for other bright pixels in the same row.

                for other_col_index in range(number_of_cols):
                    if other_col_index != col_index and picture[row_index][other_col_index] == 'B':
                        is_lonely = False
                        break
                
                if is_lonely:
                    # Check for other bright pixels in the same column.

                    for other_row_index in range(number_of_rows):
                        if other_row_index != row_index and picture[other_row_index][col_index] == 'B':
                            is_lonely = False
                            break
                
                if is_lonely:
                    lonely_pixel_count += 1

    return lonely_pixel_count

Big(O) Analysis

Time Complexity

O(m*n*(m+n)) – Let m be the number of rows and n be the number of columns in the picture. The algorithm iterates through each pixel of the picture which takes O(m*n) time. For each bright pixel encountered, it iterates through its row (O(n)) and then through its column (O(m)) to check for other bright pixels. Thus, for each pixel, the checks take O(n + m). Therefore, the overall time complexity is O(m*n*(m+n)).

Space Complexity

O(1) – The provided solution iterates through the image and checks rows and columns. It does not create any auxiliary data structures like arrays, lists, or hashmaps to store intermediate results or visited pixels. The algorithm uses a constant number of variables such as counters or indices regardless of the size of the input image. Therefore, the space complexity is constant.

Optimal Solution

Approach

To find the lonely pixel, we don't need to check every single pixel. The trick is to focus on rows and columns. We only care about rows and columns with exactly one black pixel.

Here's how the algorithm would work step-by-step:

First, count the number of black pixels in each row.
Then, count the number of black pixels in each column.
Look at each black pixel. Check if its row has exactly one black pixel AND if its column also has exactly one black pixel.
If both conditions are true, that pixel is a lonely pixel, so count it.
Finally, return the total count of lonely pixels.

Code Implementation

def findLonelyPixel(picture): 
    number_of_rows = len(picture)
    number_of_cols = len(picture[0])

    row_counts = [0] * number_of_rows
    col_counts = [0] * number_of_cols

    # Count black pixels in each row
    for row_index in range(number_of_rows): 
        for col_index in range(number_of_cols): 
            if picture[row_index][col_index] == 'B':
                row_counts[row_index] += 1

    # Count black pixels in each column
    for col_index in range(number_of_cols):
        for row_index in range(number_of_rows):
            if picture[row_index][col_index] == 'B':
                col_counts[col_index] += 1

    lonely_pixel_count = 0

    # Only count pixels where both row and column have one black pixel
    for row_index in range(number_of_rows):

        for col_index in range(number_of_cols):

            if picture[row_index][col_index] == 'B':
                #Check that pixel's row and column have exactly one 'B'

                if row_counts[row_index] == 1 and col_counts[col_index] == 1:

                    lonely_pixel_count += 1

    return lonely_pixel_count

Big(O) Analysis

Time Complexity

O(m * n) – We are given an m x n matrix (image). First, we iterate through the rows to count black pixels which takes O(m * n) time. Then, we iterate through the columns to count black pixels, taking O(m * n) time again. Finally, we iterate through all pixels to check the lonely pixel condition based on the precomputed row and column counts, which also takes O(m * n) time. Therefore, the total time complexity is O(m * n) + O(m * n) + O(m * n), which simplifies to O(m * n).

Space Complexity

O(m + n) – The algorithm uses two arrays, one to store the number of black pixels in each row and another to store the number of black pixels in each column. If the input image is of size m x n, the row count array will have size m and the column count array will have size n. Therefore, the auxiliary space used is proportional to the sum of the number of rows and columns. This leads to a space complexity of O(m + n).

Edge Cases

Case	How to Handle
Null or empty image input	Return 0 immediately, as there are no pixels to analyze.
Image with zero rows or zero columns	Return 0, as the image is effectively empty.
Image with only one row or only one column	Iterate through the single row or column and check if any 'B' appears exactly once.
Image with all 'W' pixels	Return 0, as there are no black pixels to consider.
Image with all 'B' pixels	Return 0, as no pixel will be the only one in its row or column unless the image is 1x1.
Image with a single 'B' pixel	Return 1, as this pixel is the only one in its row and column.
Large image (e.g., 200x200) to test performance	Ensure the solution uses an efficient algorithm (e.g., O(m*n)) to avoid timeouts.
Integer overflow when counting black pixels in a row or column	Since the problem statement constraints limit row and column size, integer overflow isn't a practical concern.

Null or empty image input

How to Handle:

Return 0 immediately, as there are no pixels to analyze.

Image with zero rows or zero columns

How to Handle:

Return 0, as the image is effectively empty.

Image with only one row or only one column

How to Handle:

Iterate through the single row or column and check if any 'B' appears exactly once.

Image with all 'W' pixels

How to Handle:

Return 0, as there are no black pixels to consider.

Image with all 'B' pixels

How to Handle:

Return 0, as no pixel will be the only one in its row or column unless the image is 1x1.

Image with a single 'B' pixel

How to Handle:

Return 1, as this pixel is the only one in its row and column.

Large image (e.g., 200x200) to test performance

How to Handle:

Ensure the solution uses an efficient algorithm (e.g., O(m*n)) to avoid timeouts.

Integer overflow when counting black pixels in a row or column

How to Handle:

Since the problem statement constraints limit row and column size, integer overflow isn't a practical concern.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the image (number of rows and columns), and what are the maximum possible values for these dimensions?
Are the pixel values guaranteed to be only 'W' and 'B', or could there be other characters?
If there are no lonely pixels, what should the function return?
Is it possible for the input image to be null or empty?
By 'same row and column', do you mean there can only be *one* 'B' pixel in the entire row and column, or is it okay if there are zero 'B' pixels (i.e., the row or column is all 'W')?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each pixel in the picture, one at a time.
If a pixel is bright, check all other pixels in the same row.
If you find another bright pixel in the same row, the original pixel is not lonely, so move on.
If you don't find any other bright pixels in the same row, then check all other pixels in the same column.
If you find another bright pixel in the same column, the original pixel is not lonely, so move on.
If you don't find any other bright pixels in the same column, the original pixel is lonely.
Keep a count of all the lonely pixels you find.

Code Implementation

def lonely_pixel_i_brute_force(picture):
    number_of_rows = len(picture)
    number_of_cols = len(picture[0]) if number_of_rows > 0 else 0
    lonely_pixel_count = 0

    for row_index in range(number_of_rows):
        for col_index in range(number_of_cols):
            if picture[row_index][col_index] == 'B':
                is_lonely = True
                # Check for other bright pixels in the same row.

                for other_col_index in range(number_of_cols):
                    if other_col_index != col_index and picture[row_index][other_col_index] == 'B':
                        is_lonely = False
                        break
                
                if is_lonely:
                    # Check for other bright pixels in the same column.

                    for other_row_index in range(number_of_rows):
                        if other_row_index != row_index and picture[other_row_index][col_index] == 'B':
                            is_lonely = False
                            break
                
                if is_lonely:
                    lonely_pixel_count += 1

    return lonely_pixel_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To find the lonely pixel, we don't need to check every single pixel. The trick is to focus on rows and columns. We only care about rows and columns with exactly one black pixel.

Here's how the algorithm would work step-by-step:

First, count the number of black pixels in each row.
Then, count the number of black pixels in each column.
Look at each black pixel. Check if its row has exactly one black pixel AND if its column also has exactly one black pixel.
If both conditions are true, that pixel is a lonely pixel, so count it.
Finally, return the total count of lonely pixels.

Code Implementation

def findLonelyPixel(picture): 
    number_of_rows = len(picture)
    number_of_cols = len(picture[0])

    row_counts = [0] * number_of_rows
    col_counts = [0] * number_of_cols

    # Count black pixels in each row
    for row_index in range(number_of_rows): 
        for col_index in range(number_of_cols): 
            if picture[row_index][col_index] == 'B':
                row_counts[row_index] += 1

    # Count black pixels in each column
    for col_index in range(number_of_cols):
        for row_index in range(number_of_rows):
            if picture[row_index][col_index] == 'B':
                col_counts[col_index] += 1

    lonely_pixel_count = 0

    # Only count pixels where both row and column have one black pixel
    for row_index in range(number_of_rows):

        for col_index in range(number_of_cols):

            if picture[row_index][col_index] == 'B':
                #Check that pixel's row and column have exactly one 'B'

                if row_counts[row_index] == 1 and col_counts[col_index] == 1:

                    lonely_pixel_count += 1

    return lonely_pixel_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty image input	Return 0 immediately, as there are no pixels to analyze.
Image with zero rows or zero columns	Return 0, as the image is effectively empty.
Image with only one row or only one column	Iterate through the single row or column and check if any 'B' appears exactly once.
Image with all 'W' pixels	Return 0, as there are no black pixels to consider.
Image with all 'B' pixels	Return 0, as no pixel will be the only one in its row or column unless the image is 1x1.
Image with a single 'B' pixel	Return 1, as this pixel is the only one in its row and column.
Large image (e.g., 200x200) to test performance	Ensure the solution uses an efficient algorithm (e.g., O(m*n)) to avoid timeouts.
Integer overflow when counting black pixels in a row or column	Since the problem statement constraints limit row and column size, integer overflow isn't a practical concern.

Null or empty image input

How to Handle:

Return 0 immediately, as there are no pixels to analyze.

Image with zero rows or zero columns

How to Handle:

Return 0, as the image is effectively empty.

Image with only one row or only one column

How to Handle:

Iterate through the single row or column and check if any 'B' appears exactly once.

Image with all 'W' pixels

How to Handle:

Return 0, as there are no black pixels to consider.

Image with all 'B' pixels

How to Handle:

Return 0, as no pixel will be the only one in its row or column unless the image is 1x1.

Image with a single 'B' pixel

How to Handle:

Return 1, as this pixel is the only one in its row and column.

Large image (e.g., 200x200) to test performance

How to Handle:

Ensure the solution uses an efficient algorithm (e.g., O(m*n)) to avoid timeouts.

Integer overflow when counting black pixels in a row or column

How to Handle:

Since the problem statement constraints limit row and column size, integer overflow isn't a practical concern.