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) {
movesQueue.add(new Move(C, D, 0));
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];
    Queue<Pair> bfs = new LinkedList<>();
    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.