Dynamic programming is a technique used in solving problems bottom-up (or top-down), and use solutions from overlapping subproblems to build up our larger solutions. In this example, if we figure out that we can make a small 2x2 grouping, can we use that to form larger groupings?
Kadane's Algorithm in 1D
Kadane's algorithm finds the largest subarray in an array containing numbers in O(N) time with O(1) space. For example:
[3, 6, -1, 3, -6, -7, 3, 15, -432, 2] Largest subarray => [3, 15] => 3+15 => 18
This can be computed efficient by taking into consideration the following facts which are at the core of Kadane's algorithm:
- Start iterating through the array
- Keep a cumulative sum
- If, so far, our sum is positive, we should keep our elements
- If we get a negative number, then we should start over
This is efficient, because at each iteration of Kadane's algorithm, we don't have to look back, and we use constant memory. A naive solution would have a complexity of
Relating Kadane's Algorithm to Karnaugh Maps
If we can extend Kadane's Algorithm to 2D, and instead find the largest submatrices such that all rows/columns are filled, we would solve our problem. How can this be solved? First, consider the Karnaugh Map is a grid of
1's. From before, we know that it is a filled matrix if and only if the sum is equal to width * height.
Hence, we need to extend Kadane's algorithm to 2D, taking note of the perfectly filled matrices.
Extending Algorithm to 2D
The following describes the algorithm, which takes
- Store the cumulative sums of all columns in the matrix. That is, the top-most row should contain just that item, and the row below should contain that item plus the item at its row/columns
- Start iterating through from the top row to the bottom row, called
- Start another loop, which iterates from x1 to the bottom as well, called
- Subtract, for all columns, the difference in height between
x1. This is the sum using the prefix sums array
- For the produced difference array, run 1D Kadane's algorithm
- When runnning Kadane's algorithm, do not include results who have different consecutive values in the 1D array. These potential matrices have holes with
0. Also ignore cases of illegal sizes.
The end result contains the largest matrix possible. To store the results, you can store them in a data-structure like a heap and sort based on
Math.abs(x1-x2) * Math.abs(y1-y2)
[0, 1, 0, 0 => [0, 1, 0, 0 1, 1, 1, 1 => 1, 2, 1, 1 0, 1, 1, 1 => 1, 3, 2, 1 0, 0, 1, 0] => 1, 3, 3, 1]
Following the algorithm previously illustrated, we first store the cumulative sums going down the columns. We then iterate through the indices with our
So we first get
[0, 1, 0, 0] as our array, with
x1 = 0 and
x2 = 1, which we consider
1 to be the largest. We know it is
1x1 in size because (
x2-x1=1) and we cover a range of
We then extend this further, increasing
x2 until we get to
4, then increment
x1 by one and repeat, resulting in
O(N^2) time before invoking 1D Kadane's algorithm, which takes
When we get
x2=3, we have
[0, 2, 2, 1], which gives us
[2, 2] with
x2-x1=2, hence we have our maximum here being a grouping of 4.
We can have several algorithms for storing the results. The easiest way is to store another 2D grid with the maximum pairing so far that encompasses that specific grid cell. If your new candidate is larger and it satisfies, you can set that grid. Else, you can discard it unless another cell requires it to be occupied. This will result in
O(N*M) memory, which is optimal.