How to solve java.lang.OutOfMemoryError about this code

Question

This is a simple task that sum elements in matrix in 'zigzag' move by horizontal. The variable 'sumPath' need to be long and it throw me 'java.lang.OutOfMemoryError'.

I have two 'for' cycles and need to shorten them.

How I could do it ?

Here is the code:

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int n = Integer.parseInt(scanner.next());
    int m = Integer.parseInt(scanner.next());
    int[][] matrix = new int[n][m];
    long sumPath = 1;

    matrix[0][0] = 1;
    for (int row = 0; row < n; row++) {
        if (row > 0) {
            matrix[row][0] = matrix[row - 1][0] + 3;
        }
        for (int col = 1; col < m; col++) {
            matrix[row][col] = matrix[row][col - 1] + 3;
        }
    }
    int row = 0;
    while (row < n-1) {
        for (int col = 1; col < m; col++) {
            if (col % 2 == 0) {

                sumPath = sumPath + matrix[row][col];
            } else {

                sumPath = sumPath + matrix[row+1][col];
            }
        }
        row = row + 2;
        if (row >= n) {
            break;
        }
        for (int col = m - 2; col >= 0; col--) {
            if (col % 2 == 0) {

                sumPath = sumPath + matrix[row][col];

            } else {

                sumPath = sumPath + matrix[row-1][col];

            }
        }
    }
    System.out.println(sumPath);
 }
}

Which line is throwing the exception? Is the matrix too big? — Andrew S, Dec 01 '18 at 17:56
You need to read the OutOfMemoryError to see which line is taking too much memory, then you need to work out how much memory you expect it to be using and make sure you have plenty for what you are going to use. — Peter Lawrey, Dec 01 '18 at 18:24

score 0 · Answer 1 · answered Dec 01 '18 at 19:42

There is only one line of code where an OutOfMemoryException is likely to occur:

 int[][] matrix = new int[n][m];

The matrix must fit completely into memory. When the numbers n and m are too big, the matrix will become too large for the available memory.

Oleg Cherednik · Accepted Answer · 2018-12-01T20:23:14.337

Definitely, that you have OutOfMemoryError when you initialize an array

int[][] matrix = new int[n][m]

For big n and m it is pissible (e.g. with default settings of JVM, you definetly get this exceptions for n = m = 100_000).

But notice, that you do not have to create whole array. When you calculate your path, you use only limited amount of matrix's cell and you can calculate it only when you need it.

private static final int ZERO = 1;
private static final int OFFS = 3;

public static int get(int row, int col) {
    int val = ZERO;

    for (int i = 0; i < row; i++)
        val += OFFS;

    for (int i = 0; i < col; i++)
        val += OFFS;

    return val;
}

Yes, it will be slower that creating matrix, but definetly protects you from OutOfMemoryError. To increae speed, you coud cache calculated values:

private static final Map<Integer, Map<Integer, Integer>> MAP = new HashMap<>();

public static int get(int row, int col) {
    Map<Integer, Integer> values = MAP.computeIfAbsent(row, k -> new HashMap<>());

    if (!values.containsKey(col)) {
        int val = ZERO;

        for (int i = 0; i < row; i++)
            val += OFFS;

        for (int i = 0; i < col; i++)
            val += OFFS;

        values.put(col, val);
    }

    return values.get(col);
}

P.S. This is how your solution could look:

public static void main(String... args) {
    try (Scanner scan = new Scanner(System.in)) {
        System.out.print("Height: ");
        int height = scan.nextInt();

        System.out.print("Width: ");
        int width = scan.nextInt();

        System.out.println(calcSumPath(height, width));
    }
}

private static long calcSumPath(int height, int width) {
    long sumPath = ZERO;
    int row = 0;

    while (row < height - 1) {
        for (int col = 1; col < width; col++)
            sumPath += get(col % 2 == 0 ? row : row + 1, col);

        row += 2;

        if (row >= height)
            break;

        for (int col = width - 2; col >= 0; col--)
            sumPath += get(col % 2 == 0 ? row : row - 1, col);
    }

    return sumPath;
}

private static final int ZERO = 1;
private static final int OFFS = 3;
private static final Map<Integer, Map<Integer, Integer>> MAP = new HashMap<>();

public static int get(int row, int col) {
    Map<Integer, Integer> values = MAP.computeIfAbsent(row, k -> new HashMap<>());

    if (!values.containsKey(col)) {
        int val = ZERO;

        for (int i = 0; i < row; i++)
            val += OFFS;

        for (int i = 0; i < col; i++)
            val += OFFS;

        values.put(col, val);
    }

    return values.get(col);
}

Thank you for this solution, but it is too slow – slaviyy Dec 02 '18 at 15:23 — slaviyy, Dec 02 '18 at 15:23

How to solve java.lang.OutOfMemoryError about this code

2 Answers2