Technical Interview: Longest Non-Decreasing Subsequence in MxN Matrix [closed]

Question

I was recently asked this question in a technical interview. Here is my solution. http://pastebin.com/JMVHcfRq Did I make a mistake or is there a better solution?

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals) in a rectangular grid of numbers in a language of your choice. The solution should handle grids of arbitrary width and height.
For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.
8 2 4
0 7 1
3 7 9
The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.
Write a method, in a language of your choice, that takes a rectangular grid of numbers as input, and returns the length of the longest such sequence as output.

Answer 1

You can model your problem with directed graph:

Each cell is vertex in your graph and there is an edge from C_i,j→C_k,m if two cells C_i,j,C_k,m are adjacent and C_i,j < C_k,m.

Now your problem is finding longest path in this graph, but this graph is Directed acyclic graph, because as problem says there isn't repeated number in matrix also "<" relation is anti symmetric. So your problem reduced to find longest path in directed acyclic graph, which is easy by first doing topological sort then finding longest path . e.g see this.

Update: At first glance I thought is impossible to have equal neighbors but now I see is possible, In the above graph construction we should replace < with <= then sure graph is not acyclic but still problem is equal to find the longest path in this graph.

P.S1: If I have any polynomial answer for this longest path problem I'll bring it here, but may be by this classification of problem is easier to search around it.

P.S2: as mbeckish mentioned in comments, the longest path problem is NP-Hard in general graph, but I think in this special case can be solved in P, but I don't have exact algorithm right now.

P.S3: I do a little research on it, I saw, Hamiltonian path in grid graph is NP-Complete, So seems your problem is also NP-Complete (I don't have reduction right now but they are very close to each other).

Answer 2

Your solution takes exponential time (in the size of the matrix) in the worst case.

To speed it up, use memoization, or bottom-up dynamic programming.

Answer 3

Also using n dijkstra calls (reverse it to find max path) you can solve it in O(n^3). Using a max heap can lower it to 0(n^2 log n). When building the graph, only create edges to neighbors that are >= to the current vertex.

I tried the topological sorting but I found cycles in the graph. Need to check my code.