Lonely Pixel II
MediumAsked by:
8 views
Topics:
Arrays
Given an m x n picture consisting of black and white pixels, and a non-negative integer N, find the number of black lonely pixels.
A black lonely pixel is a character 'B' that located at a specific position (i, j) and satisfies the following conditions:
- Row
iand columnjboth contain exactlyNblack pixels. - All other pixels in the same row i and column j are white (i.e.,
'W').
Example 1:
Input: picture = [["W","B","W"],
["W","B","W"],
["W","W","B"]],
N = 3
Output: 0
Explanation: There are no black lonely pixels.
Example 2:
Input: picture = [["W","B","W"],
["B","B","W"],
["W","B","W"]],
N = 1
Output: 3
Explanation:
All the three 'B' are black lonely pixels.
Example 3:
Input: picture = [["B","B","B"],
["B","B","W"],
["B","B","B"]],
N = 2
Output: 0
Constraints:
m == picture.lengthn == picture[i].length1 <= m, n <= 200picture[i][j]is'W'or'B'.0 <= N <= min(m, n)
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 is the maximum size of the image?
- What are the possible values for the pixels in the image? Are they limited to 'B' and 'W', or can there be other characters?
- If there are no 'lonely' black pixels, what should I return?
- Is a pixel considered 'lonely' if it's the only black pixel in its row AND column, or does the definition require more than one other black pixel in the row/column to NOT be lonely?
- Can I assume that the input image will always be a rectangular matrix (i.e., all rows have the same number of columns)?
Brute Force Solution
Approach
The brute force strategy for this pixel problem involves checking every possible pixel combination to find the lonely ones. We'll examine each pixel and see if it meets the specific lonely pixel criteria by comparing it to all the other pixels.
Here's how the algorithm would work step-by-step:
- Go through each pixel in the picture, one at a time.
- For the current pixel, check how many other pixels in the same row are colored.
- Also, check how many other pixels in the same column are colored.
- If the number of colored pixels in the same row is exactly a certain number, and the number of colored pixels in the same column is at least a certain number, then consider it a potential lonely pixel.
- Make sure that all the colored pixels in the column are in the specific row that is checked.
- If the pixel meets all the conditions, count it as a lonely pixel.
- Once all pixels have been checked, report the total number of lonely pixels found.
Code Implementation
def lonely_pixel_two_brute_force(picture, expected_row_colored_pixels, expected_column_colored_pixels):
number_of_lonely_pixels = 0
for row_index in range(len(picture)):
for column_index in range(len(picture[0])):
if picture[row_index][column_index] == 'B':
colored_pixels_in_row = 0
colored_pixels_in_column = 0
for k in range(len(picture[0])):
if picture[row_index][k] == 'B':
colored_pixels_in_row += 1
for k in range(len(picture)):
if picture[k][column_index] == 'B':
colored_pixels_in_column += 1
if colored_pixels_in_row == expected_row_colored_pixels and \
colored_pixels_in_column >= expected_column_colored_pixels:
# Verify all colored pixels in column
# are in the same row.
column_check = True
for k in range(len(picture)):
if picture[k][column_index] == 'B' and k != row_index:
column_check = False
break
# We only increment if the
# column check passes.
if column_check:
number_of_lonely_pixels += 1
return number_of_lonely_pixelsBig(O) Analysis
Time Complexity
O(m * n * k) – The algorithm iterates through each pixel in the picture, which is of size m * n (m rows and n columns), so that's m * n. For each pixel, it counts the number of colored pixels in the same row, taking O(n) time, and the number of colored pixels in the same column, taking O(m) time. Additionally, for each column, it checks if all the colored pixels in that column are in the current row, taking O(k) where k is number of columns to check which will be bounded by n. Thus, the time complexity is O(m * n * (n + m + k)). Simplifying to O(m * n * k) where the k is the dominant factor.
Space Complexity
O(1) – The provided plain English explanation describes iterating through the pixels and performing comparisons. No auxiliary data structures, such as arrays, lists, or hash maps, are explicitly mentioned as being created or used to store intermediate results or track visited locations. Therefore, the space complexity is dominated by a few constant space variables for loop indices and counters used to check row and column conditions. Thus, the auxiliary space used remains constant regardless of the size of the input picture, resulting in O(1) space complexity.
Optimal Solution
Approach
The most efficient way to solve this is to count how many times a black pixel appears in its row and column. Then, we focus on pixels where both row and column counts match the given numbers. This narrows down the possibilities drastically.
Here's how the algorithm would work step-by-step:
- First, go through the entire picture and count how many black pixels are in each row.
- Next, do the same thing, but this time count how many black pixels are in each column.
- Now, examine each black pixel individually.
- For each black pixel, check if its row count equals the given row number AND if its column count equals the given column number.
- If both conditions are true, it means this pixel is a lonely pixel that meets the exact requirements. Increase your counter.
- After checking all black pixels, the counter will hold the number of lonely pixels meeting the criteria. This is the final answer.
Code Implementation
def find_black_pixel(picture, target_row_count, target_column_count):
number_of_rows = len(picture)
number_of_columns = len(picture[0])
row_counts = [0] * number_of_rows
column_counts = [0] * number_of_columns
# Count black pixels in each row
for row_index in range(number_of_rows):
for column_index in range(number_of_columns):
if picture[row_index][column_index] == 'B':
row_counts[row_index] += 1
# Count black pixels in each column
for column_index in range(number_of_columns):
for row_index in range(number_of_rows):
if picture[row_index][column_index] == 'B':
column_counts[column_index] += 1
number_of_lonely_pixels = 0
# Iterate through each black pixel
for row_index in range(number_of_rows):
for column_index in range(number_of_columns):
if picture[row_index][column_index] == 'B':
# Check if the row and column counts match the target
if row_counts[row_index] == target_row_count and \
column_counts[column_index] == target_column_count:
# Only increment if both conditions are met.
number_of_lonely_pixels += 1
return number_of_lonely_pixelsBig(O) Analysis
Time Complexity
O(m * n) – The algorithm first iterates through the entire picture to count black pixels in each row. This takes O(m * n) time where m is the number of rows and n is the number of columns. Then, it iterates through the picture again to count black pixels in each column, also taking O(m * n) time. Finally, it iterates through each pixel once more to check row and column counts, which is another O(m * n) operation. Since these are sequential, 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 'm' is the number of rows and 'n' is the number of columns in the input picture, then these arrays will have sizes 'm' and 'n' respectively. Therefore, the auxiliary space required is proportional to the sum of the number of rows and columns. This results in O(m + n) space complexity where m is the number of rows and n is the number of columns.
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty picture array | Return 0 since there are no pixels to analyze. |
| Picture with zero rows or zero columns | Return 0, as a valid lonely pixel requires at least one row and one column. |
| Picture containing only '.' characters | Return 0, as there are no black pixels to be lonely. |
| Picture with only one row | Check if the row contains exactly 'N' black pixels and all corresponding column values are 'B'. |
| Picture with only one column | Check if the column contains exactly 'N' black pixels and all corresponding row values are 'B'. |
| Maximum sized input array (large number of rows and columns). | Ensure the algorithm is efficient (e.g., linear time complexity) to avoid time limit exceeded errors. |
| Large number of black pixels concentrated in a few rows/columns. | The algorithm should correctly handle this scenario and find all valid lonely pixels. |
| No lonely pixels exist in the input picture. | Return 0 in this case, indicating no lonely pixels were found. |
Null or empty picture array
How to Handle:
Return 0 since there are no pixels to analyze.
Picture with zero rows or zero columns
How to Handle:
Return 0, as a valid lonely pixel requires at least one row and one column.
Picture containing only '.' characters
How to Handle:
Return 0, as there are no black pixels to be lonely.
Picture with only one row
How to Handle:
Check if the row contains exactly 'N' black pixels and all corresponding column values are 'B'.
Picture with only one column
How to Handle:
Check if the column contains exactly 'N' black pixels and all corresponding row values are 'B'.
Maximum sized input array (large number of rows and columns).
How to Handle:
Ensure the algorithm is efficient (e.g., linear time complexity) to avoid time limit exceeded errors.
Large number of black pixels concentrated in a few rows/columns.
How to Handle:
The algorithm should correctly handle this scenario and find all valid lonely pixels.
No lonely pixels exist in the input picture.
How to Handle:
Return 0 in this case, indicating no lonely pixels were found.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
