# Out of memory error

#1

Here is my java solution which works fine but compiler says OOM. Can someone help me identify the issue with this code ?

public int knight(int A, int B, int C, int D, int E, int F) {
if (A > 0 && B > 0 && C > 0 && D > 0 && C <= A && D <= B && E > 0 && F > 0 && E <= A && F <= B) {
boolean[][] visited = new boolean[A + 1][B + 1];
while (!movesQueue.isEmpty()) {
Move move = movesQueue.remove();
visited[move.x][move.y] = true;
int moveCount = move.moveCount + 1;
if (move.x == E && move.y == F)
return moveCount - 1;
if (move.x + 2 <= A && move.y + 1 <= B && visited[move.x + 2][move.y + 1] != true) {
movesQueue.add(new Move(move.x + 2, move.y + 1, moveCount));
}
if (move.x + 1 <= A && move.y + 2 <= B && visited[move.x + 1][move.y + 2] != true) {
movesQueue.add(new Move(move.x + 1, move.y + 2, moveCount));
}
if (move.x - 1 > 0 && move.y + 2 <= B && visited[move.x - 1][move.y + 2] != true) {
movesQueue.add(new Move(move.x - 1, move.y + 2, moveCount));
}
if (move.x - 2 > 0 && move.y + 1 <= B && visited[move.x - 2][move.y + 1] != true) {
movesQueue.add(new Move(move.x - 2, move.y + 1, moveCount));
}
if (move.x - 2 > 0 && move.y - 1 > 0 && visited[move.x - 2][move.y - 1] != true) {
movesQueue.add(new Move(move.x - 2, move.y - 1, moveCount));
}
if (move.x - 1 > 0 && move.y - 2 > 0 && visited[move.x - 1][move.y - 2] != true) {
movesQueue.add(new Move(move.x - 1, move.y - 2, moveCount));
}
if (move.x + 1 <= A && move.y - 2 > 0 && visited[move.x + 1][move.y - 2] != true) {
movesQueue.add(new Move(move.x + 1, move.y - 2, moveCount));
}
if (move.x + 2 <= A && move.y - 1 > 0 && visited[move.x + 2][move.y - 1] != true) {
movesQueue.add(new Move(move.x + 2, move.y - 1, moveCount));
}
}
}
return -1;
}

#2

I am also getting same error in simple bfs approach.

``````public class Solution {
``````

// coordinate class >>>>
private class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
// >>>>>>

``````public int knight(int A, int B, int C, int D, int E, int F) {
// limit checks
if(C > A || D > B) {
return -1;
}
if(C == E && D == F) {
return 0;
}

C--;
D--;
E--;
F--;
boolean vis[][] = new boolean[A][B];
bfs.offer(new Pair(C, D));
bfs.offer(null);
int steps = 0;
// bfs starts
Pair pair = null;
while(!bfs.isEmpty()) {
pair = bfs.poll();

if(pair != null) {
int x = pair.x;
int y = pair.y;

// mark visited
vis[x][y] = true;

// add every possible move cell
int nbrRows[] = {-1, 1, -2, -2, -1, 1, 2, 2};
int nbrCols[] = {2, 2, 1, -1, -2, -2, -1, 1};
int k;
for(k = 0; k < 8; k++) {
int nxtRow = x + nbrRows[k];
int nxtCol = y + nbrCols[k];

if(isSafe(nxtRow, nxtCol, A, B) && !vis[nxtRow][nxtCol]) {
if(nxtRow == E && nxtCol == F)
return steps+1;

bfs.offer(new Pair(nxtRow, nxtCol));

}
}

}
else {
steps++;
if(!bfs.isEmpty()) {
bfs.offer(null);
}
}
}
return -1;

}
public static boolean isSafe(int row, int col, int A, int B) {
if(row >= 0 && row < A && col >= 0&& col < B) {
return true;
}
return false;
}
``````

}

#3

I am also facing the same problem

#4

As somebody pointed out in an earlier comment, mark visited just after pushing it into the queue. Otherwise more memory is wasted in pushing it multiple times.