How to find the largest submatrix whose values are sorted both row-wise and column-wise?

Question

Given a matrix, for example:

[[2 5 3 8 3]
 [1 4 6 8 4]
 [3 6 7 9 5]
 [1 3 6 4 2]
 [2 6 4 3 1]]

...how to find the greatest sub-matrix (i.e. with most values) in which all rows are sorted and all columns are sorted?

In the above example the solution would be the sub-matrix at (1,0)-(2,3):

  1 4 6 8     
  3 6 7 9

and its size is 8.

Answer 1

You could use recursion to get a maximised area that could fit below a given row segment, that itself has already been verified to be a non-decreasing value sequence. The found area will be guaranteed to stay within the column range of the given row segment, but could be more narrow and span several rows below the given row.

The area that will be returned can then be extended one row upwards, with the width that area already has. If the segment can not be wider, then we will have found the maximum area that can be made from a subsequence of this segment (or the full segment) combined with rows below it.

By filtering the best result from the results retrieved for all segments in all rows, we will have found the solution.

To avoid repetition of recursive calculations that had already been done for exactly the same segment, memoisation can be used (direct programming).

Here is the suggested code:

from collections import namedtuple
Area = namedtuple('Area', 'start_row_num start_col_num end_row_num end_col_num size')
EMPTY_AREA = Area(0,0,0,0,0)

def greatest_sub(matrix):
    memo = {}

    # Function that will be called recursively
    def greatest_downward_extension(row_num, start_col_num, end_col_num, depth=0):
        # Exit if the described segment has no width
        if end_col_num <= start_col_num:
            return EMPTY_AREA
        next_row_num = row_num + 1
        # Use memoisation:
        #   Derive an ID (hash) from the segment's attributes for use as memoisation key
        segment_id = ((row_num * len(matrix[0]) + start_col_num) 
                      * len(matrix[0]) + end_col_num)
        if segment_id in memo:
            return memo[segment_id]
        # This segment without additional rows is currently the best we have:
        best = Area(row_num, start_col_num, next_row_num, end_col_num,
                    end_col_num - start_col_num)
        if next_row_num >= len(matrix):
            return best
        next_row = matrix[next_row_num]
        row = matrix[row_num]
        prev_val = -float('inf')
        for col_num in range(start_col_num, end_col_num + 1):
            # Detect interruption in increasing series, 
            #    either vertically (1) or horizontally (0)
            status = (1 if col_num >= end_col_num or next_row[col_num] < row[col_num]
                    else (0 if next_row[col_num] < prev_val
                    else -1))
            if status >= 0: # There is an interruption: stop segment
                # Find largest area below current row segment, within its column range
                result = greatest_downward_extension(next_row_num,
                                                     start_col_num, col_num)
                # Get column range of found area and add that range from the current row
                size = result.size + result.end_col_num - result.start_col_num
                if size > best.size:
                    best = Area(row_num, result.start_col_num, 
                                result.end_row_num, result.end_col_num, size)
                if col_num >= end_col_num:
                    break
                # When the interruption was vertical, the next segment can only start
                #    at the next column (status == 1)
                start_col_num = col_num + status
            prev_val = row[col_num]
        memo[segment_id] = best
        return best

    # For each row identify the segments with non-decreasing values
    best = EMPTY_AREA
    for row_num, row in enumerate(matrix):
        prev_val = -float('inf')
        start_col_num = 0
        for end_col_num in range(start_col_num, len(row) + 1):
            # When value decreases (or we reached the end of the row), 
            #   the segment ends here
            if end_col_num >= len(row) or row[end_col_num] < prev_val:
                # Find largest area below current row segment, within its column range
                result = greatest_downward_extension(row_num, start_col_num, end_col_num)
                if result.size > best.size:
                    best = result
                if end_col_num >= len(row):
                    break
                start_col_num = end_col_num
            prev_val = row[end_col_num]
    return best

# Sample call    
matrix = [
    [2, 5, 3, 8, 3],
    [1, 4, 6, 8, 4],
    [3, 6, 7, 9, 5],
    [1, 3, 6, 4, 2],
    [2, 6, 4, 3, 1]]

result = greatest_sub(matrix)
print(result)

The output for the sample data will be:

Area(start_row_num=1, start_col_num=0, end_row_num=3, end_col_num=4, size=8)

Answer 2

One approach, which it sounds like you have tried, would be using brute force recursion to check first the entire matrix, then smaller and smaller portions by area until you found one that works. It sounds like you already tried that, but you may get different results depending on whether you check from smallest to largest sections (in which case you would have to check every combination no matter what) or largest to smallest (in which case you would still end up checking a very large number of cases).

Another approach would be to create two matrices with the same dimensions as the original, where each slot in the matrix represents the gap between two numbers and the first slot in each row or column represents the gap above the first number in said row or column. You could fill the first matrix with ones and zeros to represent whether or not a matrix could be formed vertically (a 1 representation of a gap would mean that the number lower than the gap would be larger than the number above the gap) and the second with ones or zeros to represent a similar condition horizontally. You could use AND(a,b) (in other words a binary operation where only 1 1 maps to 1) for each value in the matrix to make a matrix that would essentially be AND(matrix1,matrix2), and then you could find the largest rectangle of ones in the matrix.

Example matrix (smaller for simplicity and convenience):

[ 1 2 5 ]
[ 4 9 2 ]
[ 3 6 4 ]

Vertical matrix: a one in location L means that the number in position L is greater than the number directly above L, or that L is the top of the column (with brackets signifying that the first row will always fit the vertical conditions).

{ 1 1 1 } 
[ 1 1 0 ]
[ 0 0 1 ]

Horizontal matrix: a one in location L means that the number in position L is greater than the number directly left of L, or that L is the front of the row (leftmost point) (with brackets again signifying that the first row will always fit the vertical conditions).

{1} [ 1 1 ]
{1} [ 1 0 ]
{1} [ 1 0 ]

Vertical AND Horizontal (you could ignore the vertical-only and horizontal-only steps and do this at once: for each cell, put in a 0 if the number is larger than the number on its right or directly below it, otherwise put in a 1)

[ 1 1 1 ]
[ 1 1 0 ]
[ 0 0 0 ]

The largest rectangle would be represented by the largest rectangle of ones with the same indices as the original rectangle. It should be much easier to find the largest rectangle of ones.

Hope this helps! I know I did not explain this very clearly but the general idea should be helpful. It is very similar to the idea you presented about comparing all i and i-1 digits. Let me know if it would help for me to do this for the example matrix you gave.