We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Strictly Increasing Cells in a Matrix

Difficulty: Hard

Problem Description

Given a 1-indexed m x n integer matrix mat, you can select any cell in the matrix as your starting cell. From the starting cell, you can move to any other cell in the same row or column, but only if the value of the destination cell is strictly greater than the value of the current cell. Your task is to find the maximum number of cells that you can visit in the matrix by starting from some cell.

Key Insights

  • You can only move to cells with strictly greater values.
  • Movement is allowed in the same row or column.
  • The solution involves exploring possible paths from each cell to count how many cells can be visited.
  • Dynamic programming or memoization can be used to avoid recalculating the number of cells visited from already evaluated cells.
  • Sorting the cells based on their values can help in efficiently determining valid moves.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)) for sorting and O(m * n) for the dynamic programming traversal, resulting in an overall complexity of O(m * n * log(m * n)). Space Complexity: O(m * n) for storing results of visited cells.

Solution

To solve the problem, we can use a combination of sorting and dynamic programming. First, we will store all the cells in a list along with their coordinates and sort them based on their values. Then, we will iterate through the sorted list and for each cell, we will determine the maximum number of cells that can be visited starting from that cell by checking the cells that can be reached in the same row or column. We will maintain an array to store the maximum number of cells that can be visited from each cell as we perform this traversal.

Code Solutions

def maxIncreasingCells(mat):
    from collections import defaultdict
    
    m, n = len(mat), len(mat[0])
    cells = []
    
    for i in range(m):
        for j in range(n):
            cells.append((mat[i][j], i, j))
    
    cells.sort()  # Sort cells based on their values
    dp = [[1] * n for _ in range(m)]  # dp[i][j] = max cells can be visited starting from (i, j)
    
    for value, x, y in cells:
        for dx in range(m):  # Check all rows
            if mat[dx][y] > value:
                dp[dx][y] = max(dp[dx][y], dp[x][y] + 1)
        for dy in range(n):  # Check all columns
            if mat[x][dy] > value:
                dp[x][dy] = max(dp[x][dy], dp[x][y] + 1)
    
    return max(max(row) for row in dp)
← Back to All Questions