Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges

Given an $m$ by $n$ Boolean matrix $ℳ$. Without loss of generality, $m\ge n$. Therefore, we have $n=min\{m,n\}$. We proceed with a divide and conquer strategy with a similar format to that presented in [18] for solving the Min-Corners- problem. First, we present the algorithm’s overall approach. Then, we focus on the split cases and the map construction process in more detail.

Initially, we spend $O(m\cdot n)$ time to do some preprocessing. Then, we split $ℳ$ horizontally $\left(\frac{m}{n}-1\right)$ times so that we have $\frac{m}{n}$ matrices that are $n$ by $n$. We call it a split case when we are considering positive border rectangles that stretch across the split between two vertically-adjacent or horizontally-adjacent matrices. Notice that these initial $\left(\frac{m}{n}-1\right)$ horizontal split cases are not entirely independent from each other as a rectangle could span across multiple splits. We will see that each split case takes $O(n^2)$ time to handle. In total, these initial split cases take $O(m\cdot n)$ combined time.

Now that these initial split cases have been handled, we focus on positive border rectangles that are contained solely within one of the $n$ by $n$ matrices. For each $n$ by $n$ matrix $M$, we proceed by further subdividing the problem with horizontal and vertical splits. For example, if $M$ was horizontally split into $M_{top}$ and $M_{bottom}$, then a maximum area rectangle with a positive border in $M$ is either in $M_{top}$, $M_{bottom}$, or covered by the split case where the rectangle stretches across the boundary between $M_{top}$ and $M_{bottom}$. Similar to before, each split case will take $O(n^2)$ time. Hence, by combining horizontal and vertical splits we get four subcases each with an $\frac{n}{2}$ by $\frac{n}{2}$ matrix. This leads us to the recurrence relation $t(n)=4\cdot t(\frac{n}{2})+O(n^2)$. Solving the recurrence, we get $t(n)=O(n^2\cdot \log (n))$ [8]. Therefore, since there are $\frac{m}{n}$ many $n$ by $n$ matrices to consider, the algorithm’s total runtime is $O(m\cdot n\cdot \log (n))$.

We proceed by further describing how we efficiently handle split cases. Without loss of generality, we focus on horizontal splits. For an $n$ by $n$ matrix $M$ that is horizontally split into $M_{top}$ and $M_{bottom}$, our task is to construct maps $m_{top}$ and $m_{bottom}$. As input, these maps take in pairs of column indexes $\{j_1,j_2\}$. For the Max-Area-Border problem, the map $m_{top}$ outputs the smallest row index $i$ in $M_{top}$ such that all entries between $M_{top}(i,j_1)$ and $M_{top}(i,j_2)$ are 1’s, all entries below $M_{top}(i,j_1)$ are 1’s, and all entries below $M_{top}(i,j_2)$ are 1’s. The map $m_{bottom}$ outputs the largest row index $i$ in $M_{bottom}$ such that all entries between $M_{bottom}(i,j_1)$ and $M_{bottom}(i,j_2)$ are 1’s, all entries above $M_{bottom}(i,j_1)$ are 1’s, and all entries above $M_{bottom}(i,j_2)$ are 1’s. If we are instead solving the Min-Area-Border problem, then $m_{top}$ outputs the largest row index and $m_{bottom}$ outputs the smallest.

Once we have constructed the $m_{top}$ and $m_{bottom}$ maps, we straightforwardly compute a maximum (minimum) area rectangle with a positive border that stretches across the boundary of $M_{top}$ and $M_{bottom}$. In particular, for any pair of column indexes $\{j_1,j_2\}$, if defined, the rows

and columns $\{j_1,j_2\}$ together define a positive border rectangle. We select the maximum (minimum) area rectangle among all column pairs $\{j_1,j_2\}$.

Things are a little more complex for the initial $\left(\frac{m}{n}-1\right)$ horizontal splits cases. We still construct the $m_{top}$ and $m_{bottom}$ maps for each $n$ by $n$ matrix, but we need to carefully reuse work between vertically-adjacent matrices because a rectangle could extend beyond multiple horizontal splits. To do this, we construct all of the $m_{top}$ maps in order from top to bottom, reusing the previous vertically-adjacent matrix’s $m_{top}$ map for rectangles that might spans across multiple splits. Similarly, we construct $m_{bottom}$ maps in order from bottom to top, reusing the previous matrix’s $m_{bottom}$ map.

Given an $n$ by $n$ matrix that is horizontally split into $M_{top}$ and $M_{bottom}$, all that remains is to describe how to construct the maps $m_{top}$ and $m_{bottom}$ in $O(n^2)$ time. Without loss of generality, we focus on constructing $m_{top}$ for the Max-Area-Border problem. First, we preprocess the matrix $M_{top}$ so that for any entry $M_{top}(i,j)$ we have constant time lookup of the closest $0$ value stored to the left. That is, we have constant time lookup of the largest , if it exists, such that $M_{top}(i,j^{\prime })=0$. Similarly, we need constant time lookup of the closest $0$ value stored above any entry.

Next, let a column $j_2$ be given. We demonstrate how to compute $m_{top}(\{j_1,j_2\})$ for all in $O(n)$ total time. We proceed as follows. Start with row index $i=k$ where $k-1$ is the bottom-most row with a $0$ value in column $j_2$. Then, put row index $i$ into a group (or bucket) based on its distance to the closest $0$ value to the left of entry $M_{top}(i,j_2)$. Now, increment $i$ and repeat. Row indexes with the same distance will be put into the same group. Within groups, row indexes are in ascending order.

Following this, we create a union-find data structure starting with singleton sets $\{i\}$ for each row index $i$, adding one extra row to the bottom of $M_{top}$. We iterate through column indexes starting with $j_1=1$. We consider the associated distance $d=j_2-j_1+1$. Now, we iterate in order over the rows in the distance $d$ group. For each row $i$, we perform a union between the set containing $i$ and the set containing $i+1$. Next, we perform a find on value $k$ where $k-1$ is the bottom-most row with a $0$ value in column $j_1$. Whenever we perform this find, we determine the value of $m_{top}(\{j_1,j_2\})$. Then, we increment $j_1$ and repeat until we have computed $m_{top}(\{j_1,j_2\})$ for all .

This almost works, the only issue is that the find operation needs to return the minimum element in the set. To fix this, we use an auxiliary array to store the minimum values in each set. Basically, the array will be used to map each set’s representative element to its minimum element. Furthermore, with each union operation that we perform, we will also need to perform a find operation to compute and update the new set’s minimum element.

The surprising thing about this construction is that for each column $j_2$, the resulting sequence of unions and finds is predetermined. In other words, we can apply the special case of union-find from [13] to perform these $O(n)$ operations in $O(n)$ total time. This is quite remarkable since union-find usually takes $O(n\cdot \alpha (n))$ time to perform $O(n)$ operations. Therefore, since there are $O(n)$ possible values for $j_2$, the total runtime is $O(n^2)$ for the split case.¹¹1We acknowledge an anonymous reviewer who suggested the use of this special union-find strategy for the split cases. Our original approach was to use a binary heap, but this adds a $\log (n)$ factor to the runtime. One could alternatively use a Van Emde Boas Tree instead of a binary heap to improve efficiency. For the Min-Area-Border problem, we can perform a similar strategy that achieves the same runtime where we map representative elements to maximum elements and always perform finds on the bottom-most row index. $◀$

A similar problem, denoted by Max-Perimeter-Border, for maximizing perimeter instead of area appeared in the KPI-OPEN 2017 competition [5]. A cubic time solution is known for this problem [4]. We claim that the approach from Theorem 1 can be similarly applied to improve efficiency. The essential part in proving Theorem 1 is to identify a largest rectangle with positive border that crosses the split in at most $O(n^2)$ time which makes the total runtime’s recurrence relation work as presented. To find a largest rectangle that crosses the split, we first find all of the rectangles with maximal height that cross the split. We then pick out the rectangle of largest area from these. If instead, we pick out the rectangle with largest perimeter, this will still work because the rectangle with largest perimeter must also be a rectangle of maximal height. Therefore, we have the following corollary.

Consider a non-trivial subblock matching the positive border and empty interior pattern. Suppose that its left and right edges are at column indices $(l,r)$ and its top and bottom edges are at row indices $(t,b)$. We know that from the top of the matrix to the bottom, the interaction of each row with a matching subblock can only take one of four forms:

• $\mathrm{■}$

  $F_1$: The current row is not intersecting with this subblock.

• $\mathrm{■}$

  $F_2$: The current row is hitting the top edge $t$ of this subblock.

• $\mathrm{■}$

  $F_3$: The current row is passing through the left and right edges $(l,r)$ of this subblock.

• $\mathrm{■}$

  $F_4$: The current row is hitting the bottom edge $b$ of this subblock.

It is easy to see that at any moment, there can be at most $O(n)$ subblocks matching with form $F_2$, $F_3$, or $F_4$ because a match cannot overlap within another match. We can therefore maintain a triple $(t,l,r)$ (informally called a “staple”) to represent a partial pattern match alongside a row. We can use the intervals of 1’s from the current row and the previous row to update the current triples. To handle the transitions from $F_1$ to $F_2$, we just record the current row number and the consecutive 1 intervals as $(t,l,r)$ triples for partial pattern matches. To handle the transitions from $F_2$ to $F_3$, we utilize the information from the intervals of 1’s from the previous row and the current row to break each triple $(t,l,r)$ into multiple triples $(t,l_i,r_i)$, if necessary. To handle the transitions from $F_3$ to $F_4$, we match with the intervals of 1’s of the current row to set the bottom edge $b$ for any $(t,l,r)$ and output a pattern match. We reject a partial match when we find that the interval of 1’s of the corresponding form cannot lead to a closed bottom edge. In that case, we remove the recorded triple accordingly.

We perform the updates for each type of transition mentioned above for each row and this can be done in $O(n)$ time. Therefore, the total runtime is $O(mn)$ and space usage is $O(n)$ because we only keep track of at most $O(n)$ triples at a time. Because matches are symmetrical, we can rotate the matrix if needed to ensure that $n\le m$. For space, we ignore log factors that could result from how numeric values are stored as well as additive log terms from the special case when $2^n$ is $o(m)$.$◀$

The preceding algorithm has several advantages over alternative approaches that we have explored. In particular, it scans over all of the elements of the matrix only one time, and while it is scanning across the matrix, it only uses $O(n)$ working memory. The 2nd and 4th authors implemented the algorithm from Theorem 3 in JavaScript to identify and color empty rectangles in images, as seen in Figure 1, demonstrating the algorithm’s usefulness for computer art and graphics applications [11, 3].