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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Strictly Increasing Cells in a Matrix

Number: 2818

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given a 1-indexed m x n integer matrix mat, you can begin at any cell. From a starting cell, you are allowed to move to any other cell in the same row or column, but only if the destination cell's value is strictly greater than the current cell's value. The goal is to determine the maximum number of cells you can visit by making a sequence of such moves.

Key Insights

  • We can only move from a cell to another in the same row or column if the destination value is greater.
  • The problem is a variant of longest increasing sequence but on a 2D grid with row/column moves.
  • Instead of considering direct neighbours, we are allowed to jump arbitrarily within a row or column.
  • Sorting cells by their value and using dynamic programming (DP) allows us to compute the best path lengths, while taking care of updates on each row and column.
  • Grouping cells with the same value ensures that they do not affect each other’s DP calculation (a cell can only come from a strictly smaller value).

Space and Time Complexity

Time Complexity: O(mn × log(mn)) due to sorting all cells. Space Complexity: O(m*n + m + n) for storing DP states, row and column maximums and the sorted list of cells.

Solution

We solve the problem by:

  1. Creating a list of all cell positions along with their values.
  2. Sorting the cells by value.
  3. Using dynamic programming, for a cell at (i, j), the best path (dp[i][j]) is determined by 1 plus the maximum value among the currently stored maximums for that row and column.
  4. To handle cells with the same value (since moves must be strictly increasing) we process them in groups. For each group of cells with the same value, we calculate their DP values based solely on previous groups (cells with smaller values). After processing the group, we update the maximum path values for their corresponding row and column.
  5. The final answer is the maximum DP value encountered.

Key data structures include:

  • A DP table (implicit in our calculation) stored per cell.
  • Two arrays, one for each row and one for each column, holding the best (maximum) DP value for that row/column so far.

This approach ensures that each cell’s solution builds only on previously computed states, maintaining the strictly increasing property.

Code Solutions

# Python solution using DP and sorted cell processing
class Solution:
    def maxIncreasingCells(self, mat):
        m, n = len(mat), len(mat[0])
        # Create list of all (value, row, col) tuples.
        cells = [(mat[i][j], i, j) for i in range(m) for j in range(n)]
        # Sort cells by their value.
        cells.sort(key=lambda x: x[0])
        
        # row_max[i] stores the maximum dp value in row i so far.
        row_max = [0] * m
        # col_max[j] stores the maximum dp value in column j so far.
        col_max = [0] * n
        ans = 0  # Final answer
        
        # Process cells in groups of equal values.
        idx = 0
        while idx < len(cells):
            # Process a group with same value.
            cur_val = cells[idx][0]
            group = []
            while idx < len(cells) and cells[idx][0] == cur_val:
                value, i, j = cells[idx]
                # dp value for current cell is max in its row or column + 1.
                dp = max(row_max[i], col_max[j]) + 1
                group.append((i, j, dp))
                ans = max(ans, dp)
                idx += 1
            # After processing the group, update the row and column maximums.
            for i, j, dp in group:
                row_max[i] = max(row_max[i], dp)
                col_max[j] = max(col_max[j], dp)
        return ans

# Example usage:
# sol = Solution()
# print(sol.maxIncreasingCells([[3,1],[3,4]]))  # Output: 2
← Back to All Questions