In our previous blog, we already started with the introduction to one of the problems that we are going to discuss. We will try to discuss further about the topics involved.
Let us revisit the problem statement,
Problem #1: Given an N * M integers matrix, return the length of the longest increasing path in the matrix. It is allowed to move left, right, up or down from a cell but we may not move diagonally or outside the bounds of the matrix.
This is a pretty standard problem and involves some interesting “good-to-know” concepts and hence we felt like discussing it here.
As we are concerned about traversals in this problem, it is very intuitive to visualise the matrix in the problem as a graph. The transitions can be in any of the four directions (Up, Left, Right or Down). Let us try to build our solution on the basis of the above intuitions.
Approach #1: We can assume that all the cells present in the matrix are nodes and they have edges shared with the cells adjacent to them. We can apply some graph traversal method like DFS to walk on the nodes and determine the longest path which has node values in the increasing order.
When we think about framing this solution, we will be able to figure out that we don’t need all those edges which lead from node A to node B where A.value ≥ B.value (where node.value depicts the integral value of node).
We can start our DFS traversal from each node or cell one by one and keep comparing the longest path that we find from each of those cells. This solution works because we have considered all the possible paths that can be taken as the potential candidates to our solution.
We don’t need any extra space to solve this problem other than the visited array and the traversal defining arrays (of size 4 here). Thus, the space complexity stays ~O(N * M). Since we are performing traversals from each of the N * M cells, we have our time complexity as large as ~ O((N * M) ^ 2).
Once we have reached this point, some small observations will make us feel that the above approach is a little forced.
Approach #2: If we have visited some node in some past traversal, we can be assured that the answer for it won’t be ever updated in the future. What we mean is, in the above example, if we started our traversal from node having value 1 and had we stored the answer for node having value 6 as 1, 2 as 2, and 1 as 3, it’s no use to make a traversal again from node having value 2 or 6. In other words, if we have discovered some node ‘A’ from another node ‘B’ where A.value > B.value, then we don’t need to do the same DFS traversal from node B.
On the other hand, had we started our traversal from node having value 2 and found the longest increasing path length as 2 from this node, when we discover node having value 1, all that is left is to update the answer for this node (having value 1) as maximum of the the answers stored in all the adjacent nodes having value greater than this node and the answers obtained from the rest of the paths starting from this node, if not yet discovered.
This does sound a bit confusing but it becomes obvious when we tend to use pen and paper and build the answer matrix ourselves.
The better thing that we do in this approach is that we don’t visit an already visited cell and keep comparing the maximum value of the answers for each node as they get discovered.
The time complexity is hence reduced to ~O(N * M).
The above approach uses the concept of Dynamic Programming, as we are using the already found solutions to subproblems, to build our final solution.
A good way to check if Dynamic Programming works on the given graph or not, is to check if the traversals ever get us caught up in some cycle. If they do, we cannot apply Dynamic Programming and we need to figure out some other ways to approach the problem, otherwise it might just be asking us to think in terms of memoizing our solutions at each step.
Here!! We have reached the end of this blog.
In our next article, one of the problems that we are going to discuss is given below,
Problem: Given a list of integers depicting the costs and an integer K. We are currently at the first index and want to reach the last index. The cost of using index “i” is it’s respective cost and in each move we can either jump [1…K] indices at once. Return the minimum cost to reach the last index.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of DFS and Dynamic Programming further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
More such posts can be found at :-
Approaches To Problem Solving #7 (Stack)
In our previous blog, we already started with the introduction to one of the problems that we are going to discuss. We…