I came across a problem to find the longest increasing path in a matrix. The Brute-Force solution to it is pretty straight forward:
public class Solution {
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
m = matrix.length;
n = matrix[0].length;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j));
return ans;
}
private int dfs(int[][] matrix, int i, int j) {
int ans = 0;
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
ans = Math.max(ans, dfs(matrix, x, y));
}
return ++ans;
}
}
And the time complexity for this was given as O(2^(m+n)) where m is no. of rows, and n is no. of cols in the matrix.
I'm having a hard time understanding this. The first nested for loop is O(mn) which is fine. Now each cell is treated as a root, and a DFS is done on it. However the time complexity for a DFS is O(V + E), and here V = mn and E = 4*mn, so each dfs should be O(mn), so the total time complexity should be O(mn) x O(mn) = O(m^2.n^2) right?
Note: I am aware that this is not an optimal solution and this can be memoized, however my question is about understanding time complexity in this brute for method.
Your DFS isn't O(V+E) = O(nm) because you don't have a visited set. Without this set, the paths your various branches take can overlap and duplicate work such that you can potentially explore the same vertices and traverse the same edges many times over from any given DFS call from longestIncreasingPath. A memory-less search with a branching factor of 4 is what causes exponential behavior.
For example, consider the potential worst case of a perfectly convex matrix:
6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6
The worst case path for any vertex you search is to climb diagonally to the nearest corner, and such paths are O((n+m)/2) steps long. Every vertex has up to 4 options, and as there's no shared memory in the form of a visited set between recursive calls, you get a naive 4^((n+m)/2) = 2^(n+m) worst-case complexity for DFS. It would be more precise to say that most vertices in this worst case scenario only have 2 to 3 viable neighbors to recurse into, such that the actual worst-case complexity for each search would be between sqrt(2)^(n+m) and sqrt(3)^(n+m), but the exponential run-time is the same.
If you had a visited set, you would get a complexity more like the one you alluded to in your answer. It would be O(nm*((n+m)/2)) = O(n^2*m + m^2*n) because of the restriction that paths be increasing, but without that restriction it would be O((nm)^2).