class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {

int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] pathCount = new int[m][n];
pathCount[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;

for(int i = 1; i < n; i++) {
pathCount[0][i] =
obstacleGrid[0][i] == 0 ?
pathCount[0][i-1] : 0;
}

for(int i = 1; i < m; i++){
if(obstacleGrid[i][0] == 0) {
pathCount[i][0] = pathCount[i-1][0];
} else {
pathCount[i][0] = 0;
}
}

for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 1) {
pathCount[i][j] =0;
continue;
}
if(obstacleGrid[i-1][j] == 0){
pathCount[i][j] += pathCount[i-1][j];
}
if(obstacleGrid[i][j-1] == 0){
pathCount[i][j] += pathCount[i][j-1];
}
}
}
return pathCount[m-1][n-1];
}
}

class Solution {
public int[][] updateMatrix(int[][] matrix) {

if(matrix == null
|| matrix.length == 0
|| matrix[0].length == 0)
return matrix;
int m = matrix.length;
int n = matrix[0].length;
int[][] dist = new int[m][n];
for(int[] a : dist) {
Arrays.fill(a, 10001);
}
for(int i = 0; i < m; i++) {
for(int j = 0; j< n; j++) {
if(matrix[i][j] == 0) {
dist[i][j] = 0;
} else {
if(i > 0) {
dist[i][j] =
Math.min(dist[i-1][j] + 1,
dist[i][j]);
}
if(j > 0) {
dist[i][j] =
Math.min(dist[i][j-1] + 1,
dist[i][j]);
}
}
}
}

for(int i = m-1; i >= 0; i--) {
for(int j = n-1; j >= 0; j--) {
if(i < m-1) {
dist[i][j] =
Math.min(dist[i+1][j] + 1,
dist[i][j]);
}
if(j < n-1){
dist[i][j] =
Math.min(dist[i][j+1] + 1,
dist[i][j]);
}
}
}
return dist;
}
}

class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
char[] st1 = text1.toCharArray();
char[] st2 = text2.toCharArray();
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (st1[i-1] == st2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n][m];
}
}
class Solution {
public int minFallingPathSum(int[][] arr) {
if (arr == null
|| arr.length == 0
|| arr[0].length == 0)
return 0;

int n = arr.length;

int min1, min2, minCol = 0;
for (int i = n - 2; i >= 0; i--) {
min1 = Integer.MAX_VALUE;
min2 = Integer.MAX_VALUE;

for (int j = 0; j < n; j++) {
if (arr[i + 1][j] < min1) {
min2 = min1;
min1 = arr[i + 1][j];
minCol = j;
} else if (arr[i + 1][j] < min2) {
min2 = arr[i + 1][j];
}
}

for (int j = 0; j < n; j++) {
if (j == minCol) arr[i][j] += min2;
else arr[i][j] += min1;
}
}

int result = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
result = Math.min(result, arr[0][i]);
}

return result;
}
}
class MinFallingPathSum{
public int minFallingPathSumMethod(int[][] A) {

if(A == null || A.length == 0 || A[0].length == 0) return 0;
int n = A.length;
for(int i = 1; i < n; i++) {
for(int j = 0; j < n; j++) {
int min = A[i-1][j];
if(j > 0) min = Math.min(min, A[i-1][j-1]);
if(j < n-1) min = Math.min(min, A[i-1][j+1]);
A[i][j] += min;
}
}
int result = Integer.MAX_VALUE;
for(int i : A[n-1]) {
result = Math.min(i, result);
}
return result;
}
}

Aman Agarwal

Software developer by profession, computer gamer by hobby and a foodie by heart!!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store