Longest Increasing Path in a Matrix

Photo by Stephen Leonardi on Unsplash

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

Solution

From the above example, we can see that, from every cell, we can move in at most four directions: up, down, left, and right. We will choose to move in the direction whose cell’s value is greater than the current one. We can use Depth First Search (DFS) algorithm on each cell of the matrix to calculate the maximum number of routers that can be reached from the current cell. We will keep updating the maximum reachable distance for each cell and return this value when the complete matrix has been traversed.

While effective, this approach is not very efficient as its time complexity can reach up to 2​m+n​​. This is because we keep performing duplicate calculations as the value for the same cell can get computed again in a different DFS call. To optimize this DFS, we can cache the results for each cell when its value gets computed. This way, if we encounter the same cell again, instead of calling an expensive DFS function on it, we can simply return its value from the cache. This technique is also known as Memorization.

Let’s see how we might implement this functionality:

  1. Initialize a maxPath variable and assign it a value 0.
  2. Recursively call DFS on each cell of the matrix, and update maxPath if the result of the DFS call is greater than the current maxPath value.
  3. During a DFS call, keep visiting each of the four paths from the current cell if the value in the next cell is greater than the value in the current cell.
  4. If the result for a visited cell is not calculated, we compute it and cache (or memorize) it.
  5. Otherwise, we get it from the cache directly.
  6. Finally, return the maxPath variable.

Let m be the number of rows and n be the number of columns.

Time complexity

The time complexity will be O(m×n) because, in the worst case, we’ll be traversing the complete grid of size m x n.

Space complexity

The space complexity will be O(m×n) because the cache will be of the size m x n.

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Identity Symbols for Agile Teams

NeurIPS 2020 Online Experiments: Gather Town Poster Sessions and Mementor

AWS Serverless Single Region Failover

Finding Business Logic Vulnerabilities in Source code Review

Singleton Design Pattern in Unity Programming

READ/DOWNLOAD$^ Solving Problems in Scientific Computing Using Maple and Matlab FULL BOOK PDF &…

Quotes and notes

AZURE CLOUD PLATFORM -Azure Active Directory (Article 02)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Valid Palindrome II

Leetcode Q57. Insert Interval

Validate Binary Search Tree

Leetcode 862. Shortest Subarray with Sum at Least K