Number of paths in a grid (lattice) graph

I am trying to solve a variant of the very popular question in which we find the number of distinct valid paths on a directed graph. The graph's nodes make up a m x n lattice (grid), and the edges only lead down and right. The goal is to find how many distinct paths start at the top left corner of and end in the bottom right.

So one possible path might be down m, right n.

In this variant of the problem, there is a complication. A rectangular area inside the lattice is blocked -- no paths can go through it. (The edges that would normally lead to these nodes don't exist)

I am using Dynamic Programming to solve with a time complexity of \$O(m*n)\$.

It works pretty good with small value for rows and columns but for bigger values it throws OutOfMemoryError.

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GeekForGeeks{

public static void main(String[] args) throws NumberFormatException,
IOException {
// TODO Auto-generated method stub

BufferedReader inp = new BufferedReader(
new InputStreamReader(System.in));

String[] s1 = inp.readLine().split(" ");
int row = Integer.parseInt(s1[0]);
int col = Integer.parseInt(s1[1]); // Input for the value of row &
// col

String[] s2 = inp.readLine().split(" ");
int r1 = Integer.parseInt(s2[0]);
int c1 = Integer.parseInt(s2[1]);
int r2 = Integer.parseInt(s2[2]);
int c2 = Integer.parseInt(s2[3]); // Input for the value of row &
// column of blocked path

int[][] A = new int[row][col];

for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
A[i][j] = 1;

for (int i = r1 - 1; i < r2; i++)
for (int j = c1 - 1; j < c2; j++)
A[i][j] = 0;

int answer = numOfPaths(A, row, col);
System.

It works pretty good with small value for rows and columns but for bigger values it throws OutOfMemoryError.

That's hard to believe as I can't see any allocation there besides new int[row][col], which is no problem unless the dimensions get much bigger than a few thousands. I guess they do and you'll need a smarter algorithm. As the whole computation runs top-down, you don't have to store the whole matrix. A single row should do.

// TODO Auto-generated method stub

Are you sure you need it???

String[] s1 = inp.readLine().split(" ");
int row = Integer.parseInt(s1[0]);
int col = Integer.parseInt(s1[1]); //Input for the value of row & col

Inline comments are fine as long as they belong to the command in their line. But this is a block comment and should precede the block. It could be a also a comment for s1, but not col.

int r1 = Integer.parseInt(s2[0]);

Are we supposed to guess what r1 means? What about naming it topLeft?

private static int numOfPaths(int A[][], int row,int col)
{

Java uses "Egyptian brackets" (no line break before the opening brace). There should be a space after every comma. Passing row and col is redundant as they're obtainable from A.

if( A[0][0] == 0)

Spacing! I doubt that this special case handling is necessary.

{
    return 0;
}
else
{

The nice thing about "early return" is that it allows you to handle special cases upfront without increasing the nesting depth. Your "else" after "return" is wrong.

int i,j;
for(i=0; i<col; i++)

Use for (int i=...) instead, so that the scope of every variable is as small as possible.

if( A[0][i] == 0 )
            break; // exit from the for loop, and set remaining elements the first row set to ZERO
        B[0][i] = A[0][i];

Spacing! So you first exit the loop and then (inside of the loop) set the remaining part to zero? This can't work.

But you're lucky as all int array elements are initialized to zero anyway.

I guess all what's needed is

for (i = 1; i < row; i++) {
    for (j = 1; j < col; j++) {
        if (A[i][j] != 0) {
            B[i][j] = (int) (((B[i - 1][j] % mod) + (B[i][j - 1] % mod)) % mod);
        }
    }
}

Note the formatting (done by Eclipse for free). Also note that it's recommended to always use braces (you know "goto-fail", right?).

StackExchange Code Review Q#86576, answer score: 2