Question:
What is the Longest Increasing Path in a Matrix?

To find the longest increasing path in the matrix, you must traverse the matrix while adhering to a specific condition. It means that each cell in the path must have a value larger than the previous cell. The following is the way to solve this problem by using dynamic programming:


  • Initializing a memoization matrix: You can create a matrix to store each cell's lengths of longest-increasing paths. 

  • Define a recursive function: This function helps you explore each cell’s possible;e paths while keeping track of the maximum length.

  • Use memoization to avoid redundant calculations: Whenever you explore a cell, if you've already computed its longest increasing path length, use the memoization matrix to avoid redundant calculations.


The following is the code snippet of Python of the above approach:


def longestIncreasingPath(matrix):

    if not matrix:

        return 0


    rows, cols = len(matrix), len(matrix[0])

    memo = [[0] * cols for _ in range(rows)]


    def dfs(row, col):

        if memo[row][col]:

            return memo[row][col]


        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        max_length = 1


        for dr, dc in directions:

            new_row, new_col = row + dr, col + dc

            if 0 <= new_row < rows and 0 <= new_col < cols and matrix[new_row][new_col] > matrix[row][col]:

                length = 1 + dfs(new_row, new_col)

                max_length = max(max_length, length)


        memo[row][col] = max_length

        return max_length


    longest_path = 0

    for i in range(rows):

        for j in range(cols):

            longest_path = max(longest_path, dfs(i, j))


    return longest_path


# Example usage:

matrix = [

    [9, 9, 4],

    [6, 6, 8],

    [2, 1, 1]

]

print(longestIncreasingPath(matrix))  # Output should be 4


Suggested blogs:

>>Why Typescript does not allow a union type in an array?

>>Fix: Strange compilation error with Typescript and Angular

>>What if the property 'X' does not exist on type 'FastifyContext<unknown>'?

>>How to get the type of a class property's getter/setter in TypeScript?

>>How to assign multiple const variables in a single declaration in TypeScript?

>>How to handle more than 100 cases neatly on Typescript?

>>Type inference with 'as const' IN TypeScript

>>Typescript Return argument: Tuple type or passed to rest parameter warning?

>>How can you read a Blob in Deno in TypeScript?

>>How to do Yup validation in form with TypeScript?


Submit
0 Answers
Top Questions
12-02-2024

How to use Python pattern matching to match class types?

02-02-2024

What is the Longest Increasing Path in a Matrix?

23-01-2024

Return an array of leaders in order of their appearance using Python3

26-02-2024

How to solve maximum sum problem using Python3

18-01-2024

Write a code for the function checkEvenOdd() using Python

Related Questions

Write a code for the function checkEvenOdd() using Python
img
Calculate the number of ways to parenthesize a boolean expression in Python
img
How to mock a constant value in Python?
img
How remove residual lines after merge two regions using Geopandas in python?
img
Return an array of leaders in order of their appearance using Python3
img

What Our Clients Say About Us

Client satisfaction is our ultimate goal. Here are some kind words of our precious clients they have used to express their satisfaction with our service.

Why Choose Us ?

We endow businesses with flexible engagement models based on their unique needs. Our strength lies in state-of-the-art technology and affordable consulting services. Try us for fast POCs, full-fledged applications, or technology consulting. Always available for your service.