Java DFS solution


  • 0
    E

    The solution is based on a classic Depth First Search graph traversal algorithm. We treat the matrix as a graph with every element in the matrix being a graph's vertex. Every vertex has either two, three or four neighbors, which are connected to the source vertex by the implicitly defined edges, that are: up (x - 1, y), down (x + 1, y), left (x, y - 1) and right (x, y + 1).
    We run the DFS on every vertex and record the length of the maximum increasing sequence seen so far in a global variable max. To avoid running DFS multiple times on the same vertex, we save intermediate results in an array cache[]. Note that to simplify the code I use a 1D instead of 2D array for cache[] and marked[], where every element in the 2D array corresponds to row * width + col element in a 1D array.

    public class Solution {
        // Array for keeping track of the elements, that have been visited by the dfs.
        private boolean[] marked;
        // Array for keeping track of the intermediate results.
        private int[] cache;
        // Defensive copy of the input matrix.
        private int[][] matrix;
        // The value of the maximum increasing sequence.
        private int max;
        // Height and width of the input matrix.
        private int height, width;
        
        public int longestIncreasingPath(int[][] matrix) {
            // Initialization.
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            this.height = matrix.length;
            this.width = matrix[0].length;
            this.matrix = matrix;
            // Catch, 2D -> 1D: row * width + col; 1D -> 2D: x = 1D / width, y = 1D % width.
            this.marked = new boolean[width * height];
            this.cache = new int[height * width];
            this.max = Integer.MIN_VALUE;
            
            for (int i = 0; i < width * height; i++) {
                // Run depth-first search on every element in the matrix.
                int len = dfs(i);
                max = Math.max(max, len);
            }
            return max;
        }
        
        private int dfs(int i) {
            // If we've already run dfs on the current vertex, just return the result.
            if (cache[i] > 0) return cache[i];
            // Mark the vertex as visited.
            marked[i] = true;
            int max = 1;
            // Recursively visit all neighbors that we haven't seen so far.
            for (int n : getNeighbors(i)) {
                if (!marked[n]) {
                    int len = 1 + dfs(n);
                    max = Math.max(max, len);
                }
            }
            // Save the length of the longest increasing sequence for the current element for future use by the dfs().
            cache[i] = max;
            // Clean up the dfs() path.
            marked[i] = false;
            return max;
        }
        
        // Return all neighbors of a particular element in the matrix.
        private List<Integer> getNeighbors(int i) {
            List<Integer> neighbors = new ArrayList<>();
            // Convert 1D to 2D.
            int x = i / width, y = i % width;
            // Check all neighbors (up, down, left, right).
            // If the neighbor is greater than the current element - add it to the result.
            for (int j = -1; j <= 1; j++) {
                if (j == 0) continue;
                if (isInTheGrid(x + j, y) && matrix[x + j][y] > matrix[x][y]) neighbors.add((x + j) * width + y);
                if (isInTheGrid(x, y + j) && matrix[x][y + j] > matrix[x][y]) neighbors.add(x * width + y + j);
            }
            return neighbors;
        }
        
        // Check whether indices are in the matrix.
        private boolean isInTheGrid(int x, int y) {
            return (x >= 0 && x < height && y >= 0 && y < width);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.