329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

 

class Solution {
	public int longestIncreasingPath(int[][] matrix) {
         if (matrix.length == 0) return 0;
		int max = Integer.MIN_VALUE;
		int [][] mem = new int[matrix.length][matrix[0].length];
		for (int i = 0; i < matrix.length; i++)
			Arrays.fill(mem[i], 0);
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				max = Math.max(max,helper(i, j, mem,matrix));
			}
		}

		return max;
	}


	public int helper(int x, int y, int[][] mem, int[][] matrix) {
		if (mem[x][y] != 0) {
			return mem[x][y];
		}
		int[] dx = { 0, 1, -1, 0 };
		int[] dy = { 1, 0, 0, -1 };

		for (int i = 0; i = 0 && newX = 0 && newY  matrix[x][y]) {
				mem[x][y] = Math.max(mem[x][y], helper(newX, newY,mem, matrix));
			}
		}
		return ++mem[x][y];
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s