LockInCS

Unit 4 · 20 min

4.13 Implementing 2D Array Algorithms

A 2D algorithm is a 1D algorithm plus a decision about which index stays still.

Summary, objectives and course and exam description (CED) codes

The standard two-dimensional (2D) array algorithms are the one-dimensional (1D) algorithms (minimum or maximum, sum or average, property checks, counts, consecutive pairs, duplicates, shifting, rotating and reversing) applied to the whole 2D array or to a designated row, column or other subsection. The skill is choosing which index stays fixed and which index moves.

By the end of this session you can

  • 4.13.A Develop code for standard and original algorithms for a particular context or specification that involve 2D arrays, and determine the result of these algorithms.

4.13.A4.13.A.1

Reviewed against the CED on

Know this already? Jump to the checkpoint.

1LearnThe notes, the traps and how to remember them

All examples on this page use the same data: points scored by 3 players (rows) in 4 games (columns).

game 0 game 1 game 2 game 3
player 0 12 7 15 9
player 1 4 18 11 18
player 2 20 6 13 10

1. Minimum, maximum, sum and average

The 1D algorithms work on the whole 2D array, on one designated row, on one designated column or on another subsection 4.13.A.1. For the whole array use nested loops. For one row, fix the row index. For one column, fix the column index.

int[][] pts = { {12, 7, 15, 9},
                {4, 18, 11, 18},
                {20, 6, 13, 10} };

// minimum of the whole 2D array
int min = pts[0][0];
for (int[] row : pts)
{
    for (int p : row)
    {
        if (p < min)
        {
            min = p;
        }
    }
}
System.out.println("lowest score: " + min);

// sum and average of designated row 1 (one player)
int rowSum = 0;
for (int c = 0; c < pts[1].length; c++)
{
    rowSum += pts[1][c];
}
System.out.println("player 1 average: " + (double) rowSum / pts[1].length);

// maximum of designated column 2 (one game)
int best = pts[0][2];
for (int r = 1; r < pts.length; r++)
{
    if (pts[r][2] > best)
    {
        best = pts[r][2];
    }
}
System.out.println("best in game 2: " + best);

// sum of a subsection: rows 1 to 2, columns 0 to 1
int corner = 0;
for (int r = 1; r <= 2; r++)
{
    for (int c = 0; c <= 1; c++)
    {
        corner += pts[r][c];
    }
}
System.out.println("lower-left corner total: " + corner);

Output:

lowest score: 4
player 1 average: 12.75
best in game 2: 15
lower-left corner total: 48

Watch out: the average of the whole array divides by pts.length * pts[0].length (12 elements), not by pts.length (3 rows).

2. Property checks: at least one, all, and how many

The same three yes/no algorithms from 1D arrays apply to the whole 2D array or to one part of it 4.13.A.1. “At least one” can return true at the first match, “all” can return false at the first failure, and a count must visit every element in the part.

public static boolean anyGameOver(int[][] pts, int limit)
{
    for (int[] row : pts)
    {
        for (int p : row)
        {
            if (p > limit)
            {
                return true;
            }
        }
    }
    return false;
}

public static boolean allColumnAtLeast(int[][] pts, int col, int min)
{
    for (int r = 0; r < pts.length; r++)
    {
        if (pts[r][col] < min)
        {
            return false;
        }
    }
    return true;
}

public static int countInRow(int[][] pts, int row, int limit)
{
    int count = 0;
    for (int c = 0; c < pts[row].length; c++)
    {
        if (pts[row][c] >= limit)
        {
            count++;
        }
    }
    return count;
}

int[][] pts = { {12, 7, 15, 9},
                {4, 18, 11, 18},
                {20, 6, 13, 10} };
System.out.println(anyGameOver(pts, 19));
System.out.println(allColumnAtLeast(pts, 2, 10));
System.out.println(countInRow(pts, 0, 10));

Output:

true
true
2

Every value in column 2 (15, 11, 13) is at least 10, and row 0 has two values (12 and 15) that are at least 10.

3. Consecutive pairs and duplicates

Consecutive pairs in a row are arr[r][c] and arr[r][c + 1]; in a column they are arr[r][c] and arr[r + 1][c] 4.13.A.1. Stop one index early in the direction you compare.

To detect duplicates in a row or column, compare each element with every later element in that part. For the whole 2D array, it is easiest to number the elements 0 to rows times columns minus 1 and turn each number back into a row and column with / and % 4.13.A.1.

int[][] pts = { {12, 7, 15, 9},
                {4, 18, 11, 18},
                {20, 6, 13, 10} };

// consecutive pairs in each row: count games where a player improved
int improved = 0;
for (int r = 0; r < pts.length; r++)
{
    for (int c = 0; c < pts[0].length - 1; c++)
    {
        if (pts[r][c + 1] > pts[r][c])
        {
            improved++;
        }
    }
}
System.out.println("improvements: " + improved);

// duplicates anywhere in the 2D array
int cols = pts[0].length;
int total = pts.length * cols;
boolean dup = false;
for (int i = 0; i < total; i++)
{
    for (int j = i + 1; j < total; j++)
    {
        if (pts[i / cols][i % cols] == pts[j / cols][j % cols])
        {
            dup = true;
        }
    }
}
System.out.println("duplicate score: " + dup);

Output:

improvements: 4
duplicate score: true

Row 0 improves once (7 to 15), row 1 twice (4 to 18 and 11 to 18) and row 2 once (6 to 13), so the count is 4. The value 18 appears twice, so there is a duplicate.

4. Shift, rotate and reverse a row or a column

You can shift or rotate the elements of a row left or right, or the elements of a column up or down, and reverse a row or a column 4.13.A.1. Save the element that falls off the end, move the others toward the gap, then place the saved element at the other end.

int[][] pts = { {12, 7, 15, 9},
                {4, 18, 11, 18},
                {20, 6, 13, 10} };

// rotate row 0 right by one
int last = pts[0][pts[0].length - 1];
for (int c = pts[0].length - 1; c > 0; c--)
{
    pts[0][c] = pts[0][c - 1];
}
pts[0][0] = last;

// rotate column 1 down by one
int bottom = pts[pts.length - 1][1];
for (int r = pts.length - 1; r > 0; r--)
{
    pts[r][1] = pts[r - 1][1];
}
pts[0][1] = bottom;

// reverse row 2
for (int c = 0; c < pts[2].length / 2; c++)
{
    int temp = pts[2][c];
    pts[2][c] = pts[2][pts[2].length - 1 - c];
    pts[2][pts[2].length - 1 - c] = temp;
}

for (int[] row : pts)
{
    for (int p : row)
    {
        System.out.print(p + " ");
    }
    System.out.println();
}

Output:

9 6 7 15 
4 12 11 18 
10 13 18 20

Trace it step by step:

Step Row 0 Row 1 Row 2
Start 12 7 15 9 4 18 11 18 20 6 13 10
Rotate row 0 right 9 12 7 15 4 18 11 18 20 6 13 10
Rotate column 1 down 9 6 7 15 4 12 11 18 20 18 13 10
Reverse row 2 9 6 7 15 4 12 11 18 10 13 18 20

Watch out: rotating right with a forward loop (c = 1; c < length; c++) copies the first value into every position. Move values in the direction away from the gap: start at the end that receives a value.

Lock it in: memory hooks

  • Designated row or columnFreeze one index, loop the other: a row freezes r, a column freezes c.
  • SubsectionA subsection is just different loop bounds: change where r and c start and stop.
  • Shift without losing dataSave the one that falls off, slide the others, then drop the saved one in the gap.

Common misconceptions

  • "To total one column, you need two nested loops."

    Not quite. For one designated column the column index is fixed, so one loop over the rows is enough: sum += arr[r][col].

  • "The average of a 2D array is the total divided by arr.length."

    Not quite. arr.length counts rows only. Divide by the number of elements, arr.length * arr[0].length, and use double division.

  • "Rotating a column works the same as rotating a row with the indexes copied over."

    Not quite. In a column the moving index is the row. Shifting down means arr[r][c] gets arr[r - 1][c], so loop from the bottom row upward and save the bottom value first.

Exam traps

  • Seeding a column maximum with arr[0][0] instead of arr[0][col] can give a value from the wrong column.
  • The number of elements is arr.length * arr[0].length, not arr.length.
  • Shifting a row right with a forward loop copies the first value into every position.
  • A duplicate check across the whole 2D array needs to compare each element with every later element, not just neighbors.

2PracticeRecall it, then check yourself

In 30 seconds

  1. Every 1D algorithm (min, max, sum, average, any, all, count, pairs, duplicates, shift, rotate, reverse) has a 2D version.
  2. Whole array: nested loops. One row: fix r. One column: fix c. Subsection: change the loop bounds.
  3. Initialize min or max with a real element, such as arr[0][0] or arr[0][col].
  4. For pairs, stop one index early in the direction you compare (c < arr[0].length - 1 across, r < arr.length - 1 down).
  5. Shift and rotate move toward the gap; loop in the direction that does not overwrite values you still need.

Cover this list, say the points out loud, then take the checkpoint without scrolling back up.

Checkpoint · 5 questions

Checkpoint: Implementing 2D Array Algorithms

Pick an answer to mark it. Every answer is explained, and you can try any question again. Your saved score counts first tries only, and stays in this browser.

  1. 1 Consider the following code segment. What is printed as a result of executing the code segment? 4.13.A.1 
    int[][] g = { {3, 8, 1},
              {6, 2, 10},
              {4, 7, 5} };
int total = 0;
for (int r = 0; r < g.length; r++)
{
    total += g[r][1];
}
System.out.println(total);
    Show answer

    Answer: D. The column index is fixed at 1 and r moves down the rows, so the loop adds 8 + 2 + 7 = 17, the sum of designated column 1. 18 is the sum of row 1, 13 is the sum of column 0, and 10 is the sum of the main diagonal.

  2. 2 Consider the following code segment. What is printed as a result of executing the code segment? 4.13.A.1 
    int[][] g = { {3, 8, 1},
              {6, 2, 10},
              {4, 7, 5} };
for (int r = 0; r < g.length; r++)
{
    int max = g[r][0];
    for (int c = 1; c < g[r].length; c++)
    {
        if (g[r][c] > max)
        {
            max = g[r][c];
        }
    }
    System.out.print(max + " ");
}
    Show answer

    Answer: A. For each row the maximum restarts at the first element of that row, then the inner loop keeps the largest value: 8 for row 0, 10 for row 1 and 7 for row 2. 6 8 10 lists column maximums, 8 10 10 is what happens if the maximum is not reset for each row, and 3 6 4 prints the starting values.

  3. 3 The following code segment is intended to rotate the elements of row 0 of g one position to the right. What is printed as a result of executing the code segment? 4.13.A.1 
    int[][] g = { {1, 2, 3, 4},
              {5, 6, 7, 8} };
int last = g[0][g[0].length - 1];
for (int c = 1; c < g[0].length; c++)
{
    g[0][c] = g[0][c - 1];
}
g[0][0] = last;
for (int v : g[0])
{
    System.out.print(v + " ");
}
    Show answer

    Answer: B. The forward loop copies g[0][0] into column 1, then that same value into column 2, then into column 3, so the row becomes 1 1 1 1. The saved value 4 is then placed in column 0, giving 4 1 1 1. A correct right rotation (4 1 2 3) must loop backward from the last column; 2 3 4 1 is a left rotation.

  4. 4 Consider the following code segment. What is printed as a result of executing the code segment? 4.13.A.1 
    int[][] g = { {3, 8, 1},
              {6, 15, 10},
              {4, 7, 5} };
int count = 0;
for (int[] row : g)
{
    boolean found = false;
    for (int v : row)
    {
        if (v % 5 == 0)
        {
            found = true;
        }
    }
    if (found)
    {
        count++;
    }
}
System.out.println(count);
    Show answer

    Answer: C. The code counts rows that contain at least one multiple of 5. Row 0 has none, row 1 has 15 and 10, and row 2 has 5, so 2 rows qualify. 3 is the number of elements that are multiples of 5, which is a different algorithm; found makes each row count at most once.

  5. 5 The following code segment is intended to reverse the order of the elements in column 0 of g. What is printed as a result of executing the code segment? 4.13.A.1 
    int[][] g = { {1, 2},
              {3, 4},
              {5, 6} };
for (int r = 0; r < g.length; r++)
{
    int temp = g[r][0];
    g[r][0] = g[g.length - 1 - r][0];
    g[g.length - 1 - r][0] = temp;
}
for (int r = 0; r < g.length; r++)
{
    System.out.print(g[r][0] + " ");
}
    Show answer

    Answer: B. The loop runs over every row instead of stopping halfway. At r = 0 it swaps 1 and 5, at r = 1 it swaps 3 with itself, and at r = 2 it swaps the two end values back. The column ends as 1 3 5, unchanged. 5 3 1 is what the loop would produce with the bound r < g.length / 2.

3PrevailLock it in for exam day

By the numbers

Name each list from memory, then reveal it to check. Each list shows how many items to recall.

  • Standard algorithms that use 2D array traversals nine algorithms CED 4.13.A.1
    1. minimum or maximum
    2. sum or average
    3. at least one element has a property
    4. all elements have a property
    5. number of elements with a property
    6. all consecutive pairs
    7. presence or absence of duplicates
    8. shift or rotate a row left or right or a column up or down
    9. reverse a row or column
  • Parts of a 2D array an algorithm can work on four parts CED 4.13.A.1
    1. all the elements
    2. a designated row
    3. a designated column
    4. another subsection

Key terms: flip the cards

Read the term, say the definition out loud, then flip to check. Struggling a little to remember is what makes it stick.

  • 2D arraytap to flip

    An array of arrays that stores related data in rows and columns; each element is reached with arr[row][col].

    Example and CED codes
  • Row-major ordertap to flip

    A 2D array traversal that moves across each row, left to right, before going down to the next row.

    Example and CED codes
  • Column-major ordertap to flip

    A 2D array traversal that moves down each column, top to bottom, before moving to the next column.

    Example and CED codes
  • Traversaltap to flip

    Using repetition (or recursion) to access all elements of an array or ArrayList, or an ordered sequence of them.

    Example and CED codes
  • for looptap to flip

    An iterative statement whose header has three parts: the initialization (runs once), the Boolean expression (checked before each iteration) and the update (after each iteration).

    Example and CED codes
  • Linear searchtap to flip

    A search algorithm that checks each element in order until it finds the desired value or has checked every element.

    Example and CED codes

Questions students ask

How do you find the sum of each row of a 2D array?

Use nested loops. In the outer loop (over rows) set a total to 0, add every element of the row in the inner loop, and use or print the total before the next row starts.

How do you find the largest value in one column of a 2D array?

Start with arr[0][col], then loop r from 1 to arr.length - 1 and replace the maximum when arr[r][col] is larger. The column index stays the same the whole time.

How do you reverse one row of a 2D array?

Treat arr[r] like a 1D array: swap arr[r][c] with arr[r][arr[r].length - 1 - c] while c is less than half the row length.

What 2D array algorithms are on the AP® Computer Science A exam?

Minimum and maximum, sum and average, at least one, all, count, consecutive pairs, duplicates, shifting or rotating rows and columns, and reversing rows or columns, for the whole array or a designated row, column or subsection.

Was this page helpful?

No names are ever shown, and every public comment is checked by us first. Please do not include personal details. To get a reply, email [email protected].

↑ Top

Enlarged view of the selected figure