We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Java
  3. Data Structures
  4. Java 2D Array
  5. Discussions

Java 2D Array

  • jason_e_reynolds
     + 2 comments

    There are some really good solutions in this thread, but I wanted to throw out some variations in case anyone else was curious about how Java performed using different constructs.

    I tried 4 approaches, the first 2 using conventional summation. As expected, both of these were the fastest, but what I didn't expect to see was that solution 1 had a distinct advantage over #2. (The delta was small but consistently ~ 2x). Despite this, I personally favor #2 unless performance is a major concern - strictly because it would be the easiest to maintain.

    The 3rd and 4th approaches both used the Java8 stream/lambda functionality (mostly for my curiousity). As expected both approaches were measurably slower than #1 (100-150x and 110-200x slower respectively). I would caution anyone to take too much from this as overhead in this problem(and my inexperience with streams) overwhelmed any benefit from using streams.

        // Approach 1: explicitly add the array values (TIED FASTEST)
    private static int solve1(int[][] arr) {

        int maxValue = Integer.MIN_VALUE;
        int width = arr[0].length - 2;

        for (int row = 0; row < arr.length - 2; row++) {
            for (int col = 0; col < width; col++) {

                maxValue = Math.max(maxValue,
                        arr[row][col] + arr[row][col+1] + arr[row][col+2] +
                        arr[row + 1][col + 1] +
                        arr[row+2][col] + arr[row+2][col+1] + arr[row+2][col+2]);
            }
        }
        return maxValue;
    }

    // Approach 2: Inner loop to sum top/bottom rows (2ND FASTEST)
    private static int solve2(int[][] arr) {

        int maxValue = Integer.MIN_VALUE;
        int width = arr[0].length - 2;

        int total = 0;
        for (int row = 0; row < arr.length - 2; row++) {
            for (int col = 0; col < width; col++) {

                total = arr[row + 1][col + 1]; // center
                for (int pos = col; pos < col + 3; pos++) {
                    // add the top/bottom rows
                    total += arr[row][pos] + arr[row + 2][pos];
                }

                maxValue = Math.max(maxValue, total);
            }
        }
        return maxValue;
    }

    // Approach 3: Use streams to sum top/bottom rows (2ND SLOWEST)
    private static int solve3(int[][] arr) {
        int maxValue = Integer.MIN_VALUE;
        int width = arr[0].length - 2;

        for (int row = 0; row < arr.length - 2; row++) {
            for (int j = 0; j < width; j++) {

                maxValue = Math.max(
                        maxValue,
                        Arrays.stream(arr[row], j, j + 3).sum()
                                + arr[row + 1][j + 1]
                                + Arrays.stream(arr[row + 2], j, j + 3).sum());
            }
        }

        return maxValue;
    }

    // Approach 4: Use stream to loop/sum rather than for loops (SLOWEST)
    private static int solve4(int[][] arr) {

        int width = arr[0].length - 2;
        return IntStream.range(0, arr.length - 2).map(
                (row) -> IntStream.range(0, width).map(
                        col -> Arrays.stream(arr[row], col, col + 3).sum()
                                + arr[row + 1][col + 1]
                                + Arrays.stream(arr[row + 2], col, col + 3).sum()

                ).max().getAsInt()
        ).max().getAsInt();

    }