4.13 - Implementing 2D Array Algorithms

The same standard algorithms from before (min/max, sum/average, “at least one,” “all,” counting, consecutive pairs, duplicates, shifting, reversing) apply here too, except now you can apply them to the whole grid, or to just a specific row, column, or subsection.


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// sum of the entire grid
int total = 0;
for (int[] row : grid) {
    for (int val : row) {
        total += val;
    }
}

// sum of just one row
int rowSum = 0;
for (int val : grid[1]) {
    rowSum += val;
}

// sum of just one column
int colSum = 0;
for (int row = 0; row < grid.length; row++) {
    colSum += grid[row][2]; // sum of column index 2
}

The trick for a single row, column, or subsection is to hold one index still and loop over the other:

One row r: loop c from 0 to grid[r].length - 1 and use grid[r][c]. Or just treat grid[r] as a 1D array.

One column c: loop r from 0 to grid.length - 1 and use grid[r][c].

A subsection: loop over only part of the row and column ranges.

Here are the rest of the standard algorithms. Each code block starts from the same grid.


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// maximum of the whole grid (start with a real element, not 0)
int max = grid[0][0];
for (int[] row : grid) {
    for (int val : row) {
        if (val > max) {
            max = val;
        }
    }
}
// max is 9

// average of row 1
int rowTotal = 0;
for (int val : grid[1]) {
    rowTotal += val;
}
double rowAvg = (double) rowTotal / grid[1].length; // 15 / 3 = 5.0

// sum of a subsection: the top-left 2 by 2 corner
int cornerSum = 0;
for (int r = 0; r < 2; r++) {
    for (int c = 0; c < 2; c++) {
        cornerSum += grid[r][c];
    }
}
// cornerSum is 1 + 2 + 4 + 5 = 12


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// count: how many elements in column 0 are greater than 2?
int count = 0;
for (int r = 0; r < grid.length; r++) {
    if (grid[r][0] > 2) {
        count++;
    }
}
// count is 2 (the 4 and the 7)

// at least one: does row 0 have an even number?
boolean hasEven = false;
for (int val : grid[0]) {
    if (val % 2 == 0) {
        hasEven = true;
    }
}
// true (the 2)

// all: is every element in column 2 a multiple of 3?
boolean allMultiples = true;
for (int r = 0; r < grid.length; r++) {
    if (grid[r][2] % 3 != 0) {
        allMultiples = false;
    }
}
// true (3, 6, and 9)


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// consecutive pairs: is every row in increasing order?
boolean increasing = true;
for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[r].length - 1; c++) {
        if (grid[r][c] >= grid[r][c + 1]) {
            increasing = false;
        }
    }
}
// true

// duplicates: does row 2 have any repeated values?
boolean hasDuplicate = false;
int[] row = grid[2];
for (int i = 0; i < row.length; i++) {
    for (int j = i + 1; j < row.length; j++) {
        if (row[i] == row[j]) {
            hasDuplicate = true;
        }
    }
}
// false (7, 8, and 9 are all different)

Shifting, rotating, and reversing work on one row or one column at a time:


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// rotate row 0 left: {1, 2, 3} becomes {2, 3, 1}
int first = grid[0][0];
for (int c = 0; c < grid[0].length - 1; c++) {
    grid[0][c] = grid[0][c + 1];
}
grid[0][grid[0].length - 1] = first;


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// rotate column 1 down: 2, 5, 8 (top to bottom) becomes 8, 2, 5
int last = grid[grid.length - 1][1];
for (int r = grid.length - 1; r > 0; r--) {
    grid[r][1] = grid[r - 1][1];
}
grid[0][1] = last;


int[][] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

// reverse column 0: 1, 4, 7 (top to bottom) becomes 7, 4, 1
for (int r = 0; r < grid.length / 2; r++) {
    int temp = grid[r][0];
    grid[r][0] = grid[grid.length - 1 - r][0];
    grid[grid.length - 1 - r][0] = temp;
}

To reverse a row, use the 1D reverse from 4.5 on grid[r], since a row is just a 1D array.

Back Next