Number of Increasing Paths in a Grid

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo 109 + 7.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

 

Example 1:

Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].
- Paths with length 3: [1 -> 3 -> 4].
The total number of paths is 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -> 2].
The total number of paths is 2 + 1 = 3.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 105
SOLUTION:
class Solution:
    def getNeighbours(self, i, j, m, n):
        for x, y in [(i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)]:
            if 0 <= x < m and 0 <= y < n:
                yield (x, y)
    
    def numInc(self, matrix, i, j, m, n):
        if (i, j) in self.cache:
            return self.cache[(i, j)]
        res = 1
        for x, y in self.getNeighbours(i, j, m, n):
            if matrix[x][y] > matrix[i][j]:
                curr = self.numInc(matrix, x, y, m, n)
                res += curr
        self.cache[(i, j)] = res
        return res
    
    def countPaths(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        self.cache = {}
        res = 0
        for i in range(m):
            for j in range(n):
                res += self.numInc(matrix, i, j, m, n)
        return res % (10 ** 9 + 7)

Comments

Post a Comment

Popular posts from this blog

Encrypt and Decrypt Strings

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string. A string is encrypted with the following process: For each character c in the string, we find the index i satisfying keys[i] == c in keys . Replace c with values[i] in the string. Note that in case a character of the string is not present in keys , the encryption process cannot be carried out, and an empty string "" is returned. A string is decrypted with the following process: For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s . If there are multiple valid i , we choose any one of them. This means a string could have multiple possible strings it can decrypt t...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more

Minimum Sum of Four Digit Number After Splitting Digits

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num . Leading zeros are allowed in new1 and new2 , and all the digits found in num must be used. For example, given num = 2932 , you have the following digits: two 2 's, one 9 and one 3 . Some of the possible pairs [new1, new2] are [22, 93] , [23, 92] , [223, 9] and [2, 329] . Return the minimum possible sum of new1 and new2 .   Example 1: Input: num = 2932 Output: 52 Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc. The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52. Example 2: Input: num = 4009 Output: 13 Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.   Constraints: 1000 <= num <= 9999 SOLUTION: class Solution : def minimumSum ( self,...
Read more