CODEWITHSUNDEEP
algorithmmatrixlanguage-agnosticdynamic-programming
h4ck3d
h4ck3d

Reputation: 6364

Maximum size submatrix with same integers

There is an MxN size matrix which has integers in it. We need to find the largest size sub-matrix which has same integers in it. For example :

1 2 2 4 5
1 2 2 8 7
3 2 2 6 1

Here the largest submatrix is of 3x2 size which has all 2's in it. My idea was to check for each element arr[i][j] , whether arr[i][j+1] , arr[i+1]arr[j+1] and arr[i+1][j] are equal or not. If they are equal then we can somehow update maximum size of matrix. But I wasn't able to arrive at the exact solution.

I was wondering if somehow we can make use of Dynamic Programming. This was an interview question.

Upvotes: 2

Views: 1253

Answers (1)

kraskevich
kraskevich

Reputation: 18576

  1. Let's assume that a bottom row of the submatrix is fixed. Then each column can represented a as a pair (value, height), where value is the value of the element in this row and column and height is how many consecutive elements in this column are equal to it. For example, if the matrix is

    3 1 2 3 
1 2 2 1
3 2 2 1
2 2 2 2

    and the bottom row we are looking at is 2(in zero-based indexing), the values are (3, 1), (2, 2), (2, 3) and (1, 2), respectively.

  2. Let's split the columns into groups grouping adjacent elements with the same value together(for the previous example it would be {(3, 1)}, {(2, 2), (2, 3)} and {(1, 2)}. Now we can solve a standard problem: given an array of values h[i], find the largest value of min(h[i], h[i + 1], ..., h[j]) * (j - i + 1) for all i and j within each group(there is a linear solution that uses stacks, I can elaborate on this one if necessary). It allows us to process one row in linear time.

  3. The last thing we need is to compute the array of (value, height) for each row efficiently. For the first row it is trivial. So we can iterate over all rows and them one by one(when one element is added to the bottom of the column, (value, height) pair changes in two possible ways: it becomes either (new_value, 1) or (value, height + 1)).

These observation allow us to process one row in O(M) time. The total time complexity is O(N * M).

Here is some code(it is not a full implementation and it can contain bugs):

int solve() {
    int res = 0;
    Pair[] valueForColumn = new Pair[rowsCount];
    for (int col = 0; col < columnsCount; col++)
        valueForColunm[col] = new Pair(matrix[0][col], 1);
    res = Math.max(res, solveForRow(valueForColumn); 
    for (int row = 1; row < rowsCount; row++) {
        for (int col = 0; col < columnsCount; col++)
            if (matrix[row][col] == matrix[row - 1][col]) {
                valueForColumn[col].second++;
            } else {
                valueForColumn[col].first = matrix[row][col];
                valueForColumn[col].second = 1;
            }
        }
        res = Math.max(res, solveForRow(valueForColumn));
   }
   return res;
}

int solveForRow(Pair[] valueForColumn) {
    List<Integer> group = new ArrayList<>();
    int res = 0;
    for (int i = 0; i < valueForColumn.length; i++) {
        group.add(valueForColumn[i].second);
        if (i == valueForColumn.length - 1 
                || valueForColumn[i].first != valueForColumn[i + 1].first) {
            res = Math.max(res, solveForGroup(group));
            group.clear();
        }
    }
    return res;
}

int solveForGroup(List<Integer> heights) {
    // a stack-based algorithm 
    // with linear time complexity mentioned in 2. goes here
}

Upvotes: 2

Related Questions