Maximum Side Length of a Square with Sum Less than or Equal to Threshold: #358
Map of Highest Peak: #357
Algorithm:
The smallest rectangle area would correspond to a reactangle covering the left- and right-most points of the black pixels as well as the top and the bottom boundaries.
Approach 1-Binary Search
The intuition here is that the black pixel at the bottom is located somewhere between the given x-coordinate (coordinates for 2D-arrays aren't defined properly) and 0. If we find a black pixel in any of the pixels in the row between these, that means that we must look further down to see if there is a row with a black pixel in it. Else, we look between the middle and the x. This naturally corresponds to binary-searching all the rows between these. For the upper case, we always try to look for the upper rows. For left and right, our boundaries are not just the matrix boundaries, but the already calculated bottom and top values. While searching columns, we don't look for the pixels in those areas.
Approach 2-DFS
This approach is more straight forward but is slower, especially in cases where the majority of the image is black pixels. Since all the black pixels are connected, we can just search through the given pixel to find the boundaries. We can also mark visited nodes to '1' to save that they are visited.
Resolves: #219 Recommended problems before this: 200. Number of Islands : https://leetcode.com/problems/number-of-islands/
Algorithm:
The smallest rectangle area would correspond to a reactangle covering the left- and right-most points of the black pixels as well as the top and the bottom boundaries.
Approach 1-Binary Search
The intuition here is that the black pixel at the bottom is located somewhere between the given x-coordinate (coordinates for 2D-arrays aren't defined properly) and 0. If we find a black pixel in any of the pixels in the row between these, that means that we must look further down to see if there is a row with a black pixel in it. Else, we look between the middle and the x. This naturally corresponds to binary-searching all the rows between these. For the upper case, we always try to look for the upper rows. For left and right, our boundaries are not just the matrix boundaries, but the already calculated bottom and top values. While searching columns, we don't look for the pixels in those areas.
Approach 2-DFS
This approach is more straight forward but is slower, especially in cases where the majority of the image is black pixels. Since all the black pixels are connected, we can just search through the given pixel to find the boundaries. We can also mark visited nodes to
'1'to save that they are visited.