LC-2713 Hard LeetCode

2713. Maximum Strictly Increasing Cells in a Matrix

Array Hash Table Binary Search Dynamic Programming Memoization Sorting Matrix Ordered Set

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 31% Topics: Array, Hash Table, Binary Search, Dynamic Programming, Memoization, Sorting, Matrix, Ordered Set

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(m * n * log(m * n))
# Space: O(m * n)

import collections


# sort, dp
class Solution(object):
    def maxIncreasingCells(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: int
        """
        lookup = collections.defaultdict(list)
        for i in xrange(len(mat)):
            for j in xrange(len(mat[0])):
                lookup[mat[i][j]].append((i, j))
        dp = [[0]*len(mat[0]) for _ in xrange(len(mat))]
        row, col = [0]*len(mat), [0]*len(mat[0])
        for x in sorted(lookup.iterkeys()):
            for i, j in lookup[x]:
                dp[i][j] = max(row[i], col[j])+1
            for i, j in lookup[x]:
                row[i] = max(row[i], dp[i][j])
                col[j] = max(col[j], dp[i][j])
        return max(row)

Solution from kamyu104/LeetCode-Solutions · MIT