I'm working on the algorithm below:
Given an integer matrix, find the length of the longest increasing path.
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
My initial impulse was to have 4 functions in each direction that has an increasing value. For example, if integer 1 is in [1,1], and the four values surrounding that cell are increasing, then three functions will be created. This process, for every cell in worst case, I believe is O(4^(M*N) [4 function calls per each element, and there are mxn elements].
However, the solutions suggest the following brute force (before they go on to optimize it with memoization):
Algorithm
Each cell can be seen as a vertex in a graph G. If two adjacent cells have value a < ba<b, i.e. increasing then we have a directed edge (a, b)(a,b). The problem then becomes:
Search the longest path in the directed graph G.
Naively, we can use DFS or BFS to visit all the cells connected starting from a root. We update the maximum length of the path during search and find the answer when it finished.
Usually, in DFS or BFS, we can employ a set visited to prevent the cells from duplicate visits. We will introduce a better algorithm based on this in the next section.
Java
// Naive DFS Solution
// Time Limit Exceeded
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;
}
}
The time complexity for this algorithm which is pretty similar (just launches 4 dfs functions in the worst case for a single cell) has the following complexity analysis:
Complexity Analysis
Time complexity : O(2^{m+n))
). The search is repeated for each valid increasing path. In the worst case we can have O(2^{m+n)) calls. For example:
1 2 3 . . . n
2 3 . . . n+1
3 . . . n+2
. .
. .
. .
m m+1 . . . n+m-1
Space complexity : O(mn). For each DFS we need O(h) space used by the system stack, where hh is the maximum depth of the recursion. In the worst case, O(h) =O(mn).
I'm not following how they got this time complexity or the space complexity. For space cost, I imagine the worst case scenario is a matrix which is sorted in ascending order in rows and cols, but a single stack will be roughly proportional to the diagonal length of the mxn square. Is that why the space is worst case proportional to O(mn)? Also, how is the space cost O(2^(m+n)) and not O(4^(m*n)?
I believe Sunny is correct that brute force searches have a time complexity of O(4^(m*n)), where n and m are the numbers of rows and columns in the matrix associated with the given array. I would like to suggest a O(n*m) algorithm and Ruby code that implements it .
In problems such as this one, the tendency is to consider moving from each element in a matrix to all adjacent larger-valued elements (up to 4), and then from each of those elements to all of their adjacent larger-valued elements, and so on (hence O(4^m*n)). Because the paths must be increasing, however, we can view the problem in a different way that permits us to develop a highly-efficient optimization algorithm.
Suppose we group all the locations by value. For the example given in the question, this might be expressed:
value_to_locs
#=> { 9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]], 8=>[[1, 2]],
# 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
Next let's consider the values of the hash in decreasing order:
to_process = value_to_locs.keys.sort.reverse
#=> [9, 8, 6, 4, 2, 1]
First we process the two locations with value 9. The length of an increasing path from either of these locations is clearly 1 (the paths being [[0, 0]] and [[1, 0]]), as there's nowhere to go. We save this information to a previously-empty hash, processed, which is now:
processed = { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil } }
Next consider the single location with value 8 (the second element of to_process), [1, 2]. If an increasing path from this location has a length greater than 1 it must next go to one of the elements of processed. [1, 2] is adjacent to neither to [0, 0] nor [1, 1], so we add the key-value pair:
[1, 2]=>{ len: 1, next: nil }
to processed, obtaining
processed
#=> { [0, 0]=>{ len: 1, next: nil }, [1, 1]=>{ len: 1, next: nil },
# [1, 2]=>{ len: 1, next: nil } }
The next value (in to_process) to examine is 6, which occurs at two locations, [1, 0] and [1, 1]. The former is adjacent to one location in processed ([0, 0]), so we add to processed the key-value pair
[1, 0]=>{ len: 1 + processed[[0, 0]][:len], next: [0, 0] }
#=>{ len: 2, next: [0, 0] }
The other element with value 6, [1, 1] has two adjacent elements in processed, [0, 1] and [1, 2], so add
[1, 1]=>{ len: 1 + processed[[0, 1]][:len], next: [0, 1] }
#=>{ len: 2, next: [0, 1] }
or
[1, 1]=>{ len: 1 + processed[[1, 2]][:len], next: [1, 2] }
#=>{ len: 2, next: [1, 2] }
to processed, namely, the one for which the value of :len is greatest. (Here, it's a tie, so either can be chosen.)
We continue this way until all the elements of the original array are keys in processed. We then select as the starting point of the longest increasing path the location loc for which processed[loc][:len] is greatest, and reconstruct the associated path.
Note the key :next is needed merely to reconstruct the longest path. If only the length of the longest path is needed, that key is not needed.
Code
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
value_to_locs.keys.sort.reverse.each do |x|
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def longest_increasing_path(arr)
row_indices, col_indices = 0..arr.size-1, 0..arr.first.size-1
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
processed = {}
low, high = value_to_locs.keys.minmax
high.downto(low) do |x|
next unless value_to_locs.key?(x)
value_to_locs[x].each do |loc|
next_on_path = greater_neighbors(loc, arr, row_indices, col_indices).
max_by { |nloc| processed[nloc][:len] }
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
end
end
extract_path(processed)
end
def greater_neighbors((r,c), arr, row_indices, col_indices)
curr_val = arr[r][c]
[[-1,0], [1,0], [0,-1], [0, 1]].each_with_object([]) do |(rdelta, cdelta), a|
ra = r + rdelta
ca = c + cdelta
a << [ra, ca] if row_indices.cover?(ra) && col_indices.cover?(ca) &&
curr_val < arr[ra][ca]
end
end
def extract_path(processed)
loc, g = processed.max_by { |loc,g| g[:len] }
len = g[:len]
path = [loc]
loop do
break if g[:next].nil?
loc = g[:next]
path << loc
g = processed[loc]
end
[len, path]
end
Examples
#1
arr = [
[9,9,4],
[6,6,8],
[2,1,1]
]
longest_increasing_path(arr)
#=> [4, [[2, 1], [2, 0], [1, 0], [0, 0]]]
#2
rows = 10
cols = 10
a = (1..9).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
#=> [[4, 7, 5, 3, 5, 4, 2, 2, 9, 3],
# [8, 3, 3, 5, 4, 2, 8, 1, 8, 3],
# [7, 1, 9, 4, 2, 7, 1, 4, 4, 6],
# [3, 7, 5, 5, 2, 3, 9, 1, 9, 7],
# [2, 6, 7, 1, 5, 9, 3, 5, 2, 9],
# [4, 4, 6, 7, 8, 4, 9, 7, 6, 1],
# [9, 7, 5, 4, 6, 8, 8, 4, 4, 8],
# [3, 1, 9, 9, 5, 7, 9, 6, 7, 2],
# [5, 6, 4, 8, 2, 3, 4, 3, 3, 9],
# [7, 9, 6, 9, 5, 2, 9, 7, 6, 3]]
require 'time'
t = Time.now
longest_increasing_path(arr)
#=> [5, [[6, 3], [6, 2], [5, 2], [5, 3], [5, 4]]]
Time.now - t
#=> 0.003606 seconds
The longest path is therefore of length 5 and contains the elements 4, at [6, 3] then left to 5, up to 6, right to 7, right to 8.
#3
rows = 100
cols = 200
a = (1..20).to_a
arr = Array.new(rows) { Array.new(cols) { a.sample } }
t = Time.now
len, path = longest_increasing_path(arr)
#=> [12, [[86, 121], [86, 120], [86, 119], [87, 119], [87, 118], [86, 118],
# [85, 118], [85, 117], [86, 117], [87, 117], [88, 117], [89, 117]]]
Time.now - t
#=> 0.153562 seconds
path.map { |r,c| arr[r][c] }
#=> [1, 2, 3, 5, 7, 8, 9, 10, 11, 13, 19, 20]
Explanation
First let's consider the helper method greater_neighbors for example #1. For arr as shown,
row_indices = 0..arr.size-1
#=> 0..2
col_indices = 0..arr.first.size-1
#=> 0..2
Next, (thinking of arr as a matrix) we group locations with the same value:
value_to_locs = row_indices.each_with_object(Hash.new { |h,k| h[k] = [] }) { |r,h|
col_indices.each { |c| h[arr[r][c]] << [r,c] } }
#=> {9=>[[0, 0], [0, 1]], 4=>[[0, 2]], 6=>[[1, 0], [1, 1]],
# 8=>[[1, 2]], 2=>[[2, 0]], 1=>[[2, 1], [2, 2]]}
processed = {}
This hash will contain the locations that have been examined.
low, high = value_to_locs.keys.minmax
#=> [1, 9]
This provides the order by which locations with given values are processed, from high down to low.
enum0 = high.downto(low)
#=> #<Enumerator: 9:downto(1)>
The first element of enum0 is generated and passed to the block:
x = enum0.next
#=> 9
and
value_to_locs.key?(x)
#=> true
is executed, so we don't execute next.
We now consider all locations with the value 9, then those with value 8, and so on.
After the 9 is generated and passed to the block, and next is not executed, the following calculation is performed:
b = value_to_locs[x]
#=> [[0, 0], [0, 1]]
enum1 = b.each
#=> #<Enumerator: [[0, 0], [0, 1]]:each>
loc = enum1.next
#=> [0, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
The method greater_neighbors simply constructs an array of all locations adjacent to loc whose values are greater than the value at loc.
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> nil
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>1, :next=>nil}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}}
We now generate the next and last element of enum1 and pass it to the block:
loc = enum1.next
#=> [0, 1]
The calculations for this location are similar to those for [0, 0], resulting in:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil}}
We have reached the last element of enum1, so we next perform:
x = enum0.next
#=> 8
value_to_locs.key?(x)
#=> true # so next is not executed
b = value_to_locs[x]
#=> [[1, 2]]
enum1 = b.each
#=> #<Enumerator: [[1, 2]]:each>
loc = enum1.next
#=> [1, 2]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> []
Again, there is nowhere to go from this location, so we obtain:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}}
Continuing,
x = enum0.next
#=> 7
value_to_locs.key?(x)
#=> false # so next is executed
x = enum0.next
#=> 6
value_to_locs.key?(x)
#=> true # so next is executed
b = value_to_locs[x]
#=> [[1, 0], [1, 1]]
enum1 = b.each
#=> #<Enumerator: [[1, 0], [1, 1]]:each>
loc = enum1.next
#=> [1, 0]
c = greater_neighbors(loc, arr, row_indices, col_indices)
#=> [[0, 0]]
next_on_path = c.max_by { |nloc| processed[nloc][:len] }
#=> [0, 0]
processed[loc] = next_on_path ?
{ len: 1+processed[next_on_path][:len], next: next_on_path } :
{ len: 1, next: nil }
#=> {:len=>2, :next=>[0, 0]}
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]}}
At last, we've come to a location ([1, 0]) that is adjacent to a higher-valued location ([0, 0]).
This calculations continue in this way until we obtain:
processed
#=> {[0, 0]=>{:len=>1, :next=>nil}, [0, 1]=>{:len=>1, :next=>nil},
# [1, 2]=>{:len=>1, :next=>nil}, [1, 0]=>{:len=>2, :next=>[0, 0]},
# [1, 1]=>{:len=>2, :next=>[0, 1]}, [0, 2]=>{:len=>2, :next=>[1, 2]},
# [2, 0]=>{:len=>3, :next=>[1, 0]}, [2, 1]=>{:len=>4, :next=>[2, 0]},
# [2, 2]=>{:len=>2, :next=>[1, 2]}}
All that remains is to find the key-value pair k=>v for which v[:len] is greatest and then extract the longest path. That is done by the helper extract, which, like greater_neighbors, is straightforward.