The problem involves processing a 2D array representing an image, where each pixel is either a `0` or `1`. The array may contain one or more rectangular regions of `0`s surrounded by `1`s. The tasks are:

1. **Identify Rectangles**: Write a function that detects all rectangles of `0`s in the 2D array, returning the coordinates of the top-left and bottom-right corners for each rectangle.
2. **Handle Multiple Rectangles**: Adapt the solution to correctly identify and manage multiple separate rectangles within the image.
3. **Check Point Inside Rectangles**: Implement functionality to determine if a given point is inside any of the detected rectangles.

Question

The problem involves processing a 2D array representing an image, where each pixel is either a `0` or `1`. The array may contain one or more rectangular regions of `0`s surrounded by `1`s. The tasks are:

1. **Identify Rectangles**: Write a function that detects all rectangles of `0`s in the 2D array, returning the coordinates of the top-left and bottom-right corners for each rectangle.
2. **Handle Multiple Rectangles**: Adapt the solution to correctly identify and manage multiple separate rectangles within the image.
3. **Check Point Inside Rectangles**: Implement functionality to determine if a given point is inside any of the detected rectangles.

eng · Accepted Answer

what can you share about the onsite rounds?

Anonymous · Answer

I solved the problem by iterating through the 2D array to detect rectangles of `0`s, marking processed pixels directly in the image to avoid redundant checks. For each rectangle, I stored the coordinates of its top-left and bottom-right corners. I handled multiple rectangles by continuing the scan even after finding one. To check if a point lies within any rectangle, I added a `contains` method to the `Rectangle` class and created a function to iterate through all rectangles. This approach is efficient, minimizes extra memory usage, and keeps the code clean and modular.

Reddit

Reddit interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?