2D Array Traversals - AP Computer Science A

SECTION 1

Historical Context & Motivation

The concept of organizing data into rows and columns is as old as civilization itself — Babylonian clay tablets from 1800 BCE recorded astronomical observations in tabular form. When electronic computing emerged in the mid-twentieth century, engineers needed a way to represent these two-dimensional structures in linear memory. The 2D array became the foundational data structure for this purpose, and the algorithms that systematically visit every element — known as traversals — became essential building blocks for image processing, scientific simulation, game development, and countless other domains.

1945 • Von Neumann Architecture

John von Neumann's stored-program model establishes linear memory, requiring multi-dimensional data to be mapped into one-dimensional address spaces — the root of row-major and column-major storage.

1957 • Fortran & Column-Major Order

IBM releases Fortran, the first high-level language, which stores 2D arrays in column-major order. This choice profoundly affects traversal performance for scientific computing for decades.

1972 • C & Row-Major Order

Dennis Ritchie creates C at Bell Labs, adopting row-major storage. Java later inherits this convention, making row-major traversal the natural, cache-friendly pattern for AP Computer Science A.

1995 • Java & Arrays of Arrays

Java launches with a distinctive model: a 2D array is actually an array of references to 1D arrays, enabling jagged arrays and making the 'array of arrays' mental model central to AP CSA.

2003 • AP Computer Science A Curriculum

The College Board introduces 2D arrays as a required topic in AP CSA, solidifying row-major and column-major traversal as essential skills tested on the exam.

The central question for any 2D array algorithm is deceptively simple: in what order should we visit every element? The answer depends on the task at hand — summing all values, searching for a target, or transforming each cell — and choosing the wrong traversal order can yield incorrect results or drastically degrade performance. Understanding these traversal patterns is not only essential for the AP exam but also provides the conceptual scaffolding for more advanced topics like matrix algorithms, image convolution, and dynamic programming.

SECTION 2

Core Principles & Definitions

In Java, a 2D array is declared as int[][] matrix and is technically an array whose elements are themselves 1D arrays. Each inner array represents a row, and the elements within that row occupy consecutive columns. You access element at row r and column c via matrix[r][c]. The total number of rows is matrix.length, and the number of columns in row r is matrix[r].length. For a rectangular 2D array (which the AP exam exclusively uses), every row has the same number of columns.

Row-Major Traversal

The outer loop iterates over rows and the inner loop iterates over columns. Elements are visited left-to-right across each row before moving to the next row. This is the default and most common pattern.

Column-Major Traversal

The outer loop iterates over columns and the inner loop iterates over rows. Elements are visited top-to-bottom down each column before advancing to the next column.

Nested for Loops

Both traversal orders use two nested for loops. The outer loop controls which dimension is traversed first; the inner loop handles the other dimension. The loop bounds derive from .length.

Enhanced for Loop

A for-each loop over a 2D array yields each row (a 1D array), and a nested for-each over that row yields each element. This always performs row-major traversal and does not provide index access.

✦

KEY TAKEAWAY

Think of a 2D array as a spreadsheet. Row-major traversal reads the spreadsheet the way your eyes naturally scan text: left to right across each row, then down to the next row. Column-major traversal reads it like a newspaper column: top to bottom down one column, then over to the next column. The only difference in code is which loop is outer and which is inner.

SECTION 3

Visual Explanation: Traversal Orders

Side-by-side comparison of row-major (left, cyan) and column-major (right, violet) traversal patterns on a 3×3 grid. Solid arrows show movement within the current row or column; dashed curves show the transition to the next row or column. The code patterns below each grid show the only difference: which variable controls the outer loop.

In the diagram above, notice that both traversals visit every cell exactly once, but in different orders. For the row-major pattern, the outer loop variable r controls the row, and the inner variable c sweeps across columns — the row index changes slowly while the column index changes rapidly. For column-major traversal, the roles are swapped: c is the outer variable and r is inner, so the column index changes slowly while the row index changes rapidly. The access expression mat[r][c] remains identical in both cases — only the loop nesting differs.

SECTION 4

How 2D Array Traversals Work in Java

Declaration and Initialization

A 2D array in Java can be created with a single statement that specifies both dimensions. For example, int[][] grid = new int[3][4]; allocates a grid with 3 rows and 4 columns, all initialized to 0. Alternatively, an initializer list can populate the array directly: int[][] grid = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};. Each inner brace pair becomes one row. The compiler infers both dimensions from the structure of the literal.

Row-Major Traversal (Standard for Loop)

ROW-MAJOR PATTERN

for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[r].length; c++) // visit grid[r][c]

Here grid.length gives the number of rows, and grid[r].length gives the number of columns in row r. Using grid[r].length instead of grid[0].length is a safe habit, though both work for rectangular arrays.

Column-Major Traversal (Standard for Loop)

COLUMN-MAJOR PATTERN

for (int c = 0; c < grid[0].length; c++) for (int r = 0; r < grid.length; r++) // visit grid[r][c]

The outer loop now controls the column. Notice that the access expression grid[r][c] is unchanged — r always indexes the row and c always indexes the column, regardless of which is the outer loop.

Enhanced for Loop (Row-Major Only)

ENHANCED FOR-EACH PATTERN

for (int[] row : grid) for (int val : row) // visit val

The outer for-each yields each row as a int[] reference. The inner for-each yields each element. This always traverses in row-major order and does not expose row/column indices, making it ideal for read-only operations like summing or searching.

💡

AP Exam Tip

The AP exam frequently tests your ability to trace the output of a nested loop over a 2D array. To determine the traversal order from code alone, identify which variable is in the outer loop. If the row variable is outer, it is row-major. If the column variable is outer, it is column-major. The element access expression arr[r][c] does not change between the two patterns.

SECTION 5

Common Traversal Patterns & Algorithms

Beyond the basic row-major and column-major patterns, the AP CSA exam expects you to apply traversals to specific algorithmic tasks. The diagram below illustrates several common patterns you may encounter, including summing all elements, finding a maximum, counting occurrences, and operating on specific rows or columns.

Six common 2D array algorithm patterns you should recognize on the AP exam. Each card shows a concise code template with annotations indicating when to use indexed loops versus enhanced for-each loops.

A critical distinction for the AP exam is when to use indexed for loops versus enhanced for-each loops. You must use an indexed loop whenever the algorithm requires modifying elements in place, accessing neighboring cells, or returning the row-column position of a found element. The enhanced for-each loop is appropriate only for read-only operations — since the loop variable holds a copy of the element (for primitives), assigning to it does not modify the original array. On the AP exam, this distinction is a common source of errors in both multiple-choice tracing questions and free-response implementations.

SECTION 6

Worked Example: Row Sums and Column-Major Search

Consider the following 3×4 array and two tasks: (1) compute the sum of each row, and (2) find the first element greater than 20 using column-major traversal.

	Col 0	Col 1	Col 2	Col 3
Row 0	5	12	8	3
Row 1	17	6	25	14
Row 2	9	21	4	30

Sample 3×4 array for the worked example

Task 1: Compute Row Sums

1
Step 1 — Identify the pattern

Computing each row's sum requires a row-major traversal where we reset the accumulator at the start of each row. The outer loop iterates over rows; the inner loop sums the values across columns.
2
Step 2 — Write the code

int[] rowSums = new int[grid.length]; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[r].length; c++) { rowSums[r] += grid[r][c]; } }
3
Step 3 — Trace row 0

r = 0: rowSums[0] = 0 + 5 + 12 + 8 + 3

rowSums[0] = 28
4
Step 4 — Trace rows 1 and 2

r = 1: 17 + 6 + 25 + 14 = 62. r = 2: 9 + 21 + 4 + 30 = 64.

rowSums = {28, 62, 64}

Task 2: Column-Major Search for First Value > 20

1
Step 1 — Choose column-major order

Since the problem specifies column-major traversal, the outer loop iterates over columns (c) and the inner loop iterates over rows (r). We return the first match.
2
Step 2 — Trace column 0

c = 0: check grid[0][0] = 5 (no), grid[1][0] = 17 (no), grid[2][0] = 9 (no). No match in column 0.
3
Step 3 — Trace column 1

c = 1: check grid[0][1] = 12 (no), grid[1][1] = 6 (no), grid[2][1] = 21 (yes — 21 > 20). Return immediately.

First value > 20 is 21 at position [2][1]
4
Step 4 — Compare with row-major result

If we had used row-major traversal, the first value > 20 encountered would be 25 at [1][2], not 21. This demonstrates that traversal order determines which element is found first when there are multiple matches.

A restorer lifts a tile from a luminous rectangular mosaic. Grid algorithms turn a visual pattern into explicit row and column operations. Bounds checks determine which neighboring cells can be accessed.

The same 3-by-4 array shows column-major and row-major search paths stopping at different qualifying cells. For this 3-by-4 array, column-major search finds the first value greater than 20 at [2][1]: 21. Row-major search instead reaches 25 at [1][2] first. The row sums are 28, 62 and 64.

SECTION 7

Loop Types Compared: Strengths & Limitations

The AP CSA exam expects you to choose the appropriate loop construct for a given task. The table below compares the three loop approaches across the dimensions that matter most on the exam: index access, modification capability, traversal order flexibility, and code conciseness.

Feature	Standard for (Row-Major)	Standard for (Col-Major)	Enhanced for-each
Index access	Yes — r and c available	Yes — r and c available	No — no index variables
Modify elements	Yes — direct assignment via arr[r][c]	Yes — direct assignment via arr[r][c]	No — loop variable is a copy (primitives)
Traversal order	Row-major	Column-major	Row-major only
Partial traversal	Yes — adjust loop bounds	Yes — adjust loop bounds	Limited — cannot skip rows/cols easily
Conciseness	Moderate — requires length expressions	Moderate — requires length expressions	High — no index management
Off-by-one risk	Moderate — ensure < not <=	Moderate — ensure < not <=	Low — bounds managed automatically

Comparison of loop approaches for 2D array traversal

⚙

CHOOSING THE RIGHT LOOP

Think of the enhanced for-each loop as a read-only window into the array — you can see every value but cannot reach through the glass to change anything. Standard indexed for loops are like having a keycard that opens each cell by its coordinates, letting you both read and write. On the AP exam, default to the enhanced for-each when the problem only requires reading values (sums, counts, searches), and switch to indexed loops whenever the task involves modification, neighbor access, or column-major order.

SECTION 8

Connection to Advanced Topics

The 2D array traversal patterns you learn for AP CSA form the foundation of many advanced algorithms in computer science. Understanding how loop nesting and traversal order affect program behavior prepares you for topics in data structures, algorithms, and systems programming that you will encounter in college courses.

AP CSA Concept	Advanced Extension	Where You'll See It
Row-major traversal	Cache-friendly memory access patterns; spatial locality in CPU caches	Computer Architecture, Systems Programming
Column-major traversal	Fortran-style scientific computing; matrix transposition algorithms	Numerical Methods, Linear Algebra
Nested loops over 2D arrays	Image convolution, kernel filters, feature detection	Computer Vision, Machine Learning
2D accumulation patterns	Dynamic programming on grids (shortest paths, edit distance)	Algorithms (AP CS post-exam, college DS&A)
Searching in 2D arrays	Graph traversal (BFS/DFS on grid-based graphs)	Data Structures, AI/Game Development

How AP CSA traversal concepts extend into advanced CS

One particularly elegant connection is to dynamic programming on grids. Many classic DP problems — finding the minimum-cost path through a grid, computing edit distance between strings, or counting unique paths — rely on traversing a 2D table in a specific order so that each cell's dependencies have already been computed. The row-major and column-major patterns you master now become the scaffolding for these more sophisticated algorithms. Similarly, in image processing, every pixel in a digital image is stored in a 2D array, and operations like blurring, edge detection, and color transformation require traversals that examine each pixel and its neighbors — a direct extension of the patterns presented in this lesson.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the following code segment:

int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int c = 0; c < arr[0].length; c++)
    for (int r = 0; r < arr.length; r++)
        System.out.print(arr[r][c] + " ");

What is printed as a result of executing the code segment?

A. 1 2 3 4 5 6 7 8 9
B. 1 4 7 2 5 8 3 6 9
C. 1 2 3 4 5 6 7 8 9 (each on a new line)
D. 7 8 9 4 5 6 1 2 3

Show answer (B)

B is correct. The outer loop iterates over columns (c = 0, 1, 2) and the inner loop iterates over rows (r = 0, 1, 2), producing column-major order. For c=0: arr[0][0]=1, arr[1][0]=4, arr[2][0]=7. For c=1: arr[0][1]=2, arr[1][1]=5, arr[2][1]=8. For c=2: arr[0][2]=3, arr[1][2]=6, arr[2][2]=9. Result: 1 4 7 2 5 8 3 6 9. A is wrong because it shows row-major order (outer loop over rows), which would require r to be the outer variable. C is wrong because the code uses print, not println, so no newlines are inserted. D is wrong because it reverses the row order, which would require the row loop to count down from arr.length−1.

Question 2: BASIC

Consider the following code segment:

int[][] mat = {{10, 20}, {30, 40}, {50, 60}};
int sum = 0;
for (int[] row : mat)
    for (int val : row)
        sum += val;
System.out.println(sum);

What value is printed?

A. 90
B. 150
C. 210
D. 120

Show answer (C)

C is correct. The enhanced for-each loop visits every element in row-major order: 10 + 20 + 30 + 40 + 50 + 60 = 210. A (90) is wrong — it would be the sum of only the first column (10 + 30 + 50) or an incomplete summation. B (150) is wrong — there is no subset of these elements that sums to 150 in a natural traversal pattern. D (120) is wrong — it equals 10 + 20 + 30 + 60, which corresponds to no consistent traversal pattern.

Question 3: INTERMEDIATE

Consider the following code segment:

String[][] board = {{"X", "O", "X"},
                    {"O", "X", "O"},
                    {"X", "X", "X"}};
int count = 0;
for (int r = 0; r < board.length; r++)
    for (int c = 0; c < board[r].length; c++)
        if (r == c && board[r][c].equals("X"))
            count++;
System.out.println(count);

What is printed?

A. 2
B. 3
C. 4
D. 5

Show answer (B)

B is correct. The condition r == c restricts the check to the main diagonal elements only: board[0][0], board[1][1], and board[2][2]. • board[0][0] = "X" → equals "X" is true, count becomes 1 • board[1][1] = "X" → equals "X" is true, count becomes 2 • board[2][2] = "X" → equals "X" is true, count becomes 3 All other elements have r ≠ c, so the if condition fails and they are skipped. The final value of count is 3. Why the other answers are wrong: • A (2) — This would be correct only if one of the diagonal elements were not "X", but all three are. • C (4) — This would require four diagonal matches, but a 3×3 array has only three main diagonal positions. • D (5) — There are five total "X" values in the entire board, but the r == c condition limits checking to the diagonal only.

Question 4: APPLIED

4 pts

Write a static method public static int[] columnMaxes(int[][] grid) that returns a new array containing the maximum value in each column of grid. You may assume grid is a rectangular 2D array with at least one row and one column. For example, if grid = {{3, 7, 2}, {5, 1, 8}, {4, 9, 6}}, the method should return {5, 9, 8}.

Show answer

Point-by-point rubric: Point 1 — Create result array of correct size: Declare int[] result = new int[grid[0].length]; using the number of columns. Point 2 — Initialize each element to the first row's value: For each column c, set result[c] = grid[0][c]; (or use Integer.MIN_VALUE as the initial value). Point 3 — Use correct column-oriented traversal: Iterate through each column c and each row r (starting from row 1 if initialized from row 0), comparing grid[r][c] with result[c] and updating if greater. Point 4 — Return the result array: return result; Sample solution:

public static int[] columnMaxes(int[][] grid) {
    int[] result = new int[grid[0].length];
    for (int c = 0; c < grid[0].length; c++) {
        result[c] = grid[0][c];
        for (int r = 1; r < grid.length; r++) {
            if (grid[r][c] > result[c]) {
                result[c] = grid[r][c];
            }
        }
    }
    return result;
}

Walkthrough with grid = {{3, 7, 2}, {5, 1, 8}, {4, 9, 6}}: The result array has length 3 (number of columns). Column 0: Initialize result[0] = 3. Row 1: grid[1][0] = 5 > 3, so result[0] = 5. Row 2: grid[2][0] = 4, not greater. Final: result[0] = 5. Column 1: Initialize result[1] = 7. Row 1: grid[1][1] = 1, not greater. Row 2: grid[2][1] = 9 > 7, so result[1] = 9. Final: result[1] = 9. Column 2: Initialize result[2] = 2. Row 1: grid[1][2] = 8 > 2, so result[2] = 8. Row 2: grid[2][2] = 6, not greater. Final: result[2] = 8. Returned array: {5, 9, 8}, which matches the expected output.

Question 5: CRITICAL THINKING

3 pts

A student claims that the following method correctly doubles every element in a 2D array of integers:

public static void doubleAll(int[][] grid) {
    for (int[] row : grid)
        for (int val : row)
            val = val * 2;
}

(a) Explain why this method does NOT correctly modify the array. (b) Write a corrected version of the method that successfully doubles every element. (c) Explain why using an enhanced for loop for the outer loop (iterating over rows) IS acceptable, while using it for the inner loop (iterating over individual int values) is NOT acceptable for modification.

Show answer

Point-by-point rubric: Point 1 — Explain the bug (part a): The inner enhanced for loop assigns each int element to the local variable val. Since int is a primitive type, val is a copy of the array element, not a reference to it. Assigning val = val * 2 modifies only the local copy; the original array element remains unchanged. Point 2 — Correct implementation (part b): Replace the inner loop with an indexed for loop:

public static void doubleAll(int[][] grid) {
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[r].length; c++)
            grid[r][c] = grid[r][c] * 2;
}

Point 3 — Explain outer vs. inner for-each (part c): In the outer for-each (for (int[] row : grid)), row is a reference to the actual 1D array object stored in grid — arrays are reference types in Java. Through this reference, you CAN modify the contents of that row. However, in the inner for-each (for (int val : row)), val is a primitive int, so it is a copy. Assigning to val does not affect the array. The key distinction is reference type (int[]) vs. primitive type (int): for-each loop variables that are references allow mutation of the referenced object, while primitive loop variables are disconnected copies.

SUMMARY

2D Array Traversals — Key Concepts

Summary

A 2D array in Java is an array of arrays, accessed via arr[row][col]. The number of rows is arr.length and the number of columns in a row is arr[r].length. Row-major traversal uses the row variable as the outer loop, visiting elements left-to-right across each row. Column-major traversal uses the column variable as the outer loop, visiting elements top-to-bottom down each column. The element access expression arr[r][c] is the same in both patterns — only the loop nesting changes.

The enhanced for-each loop always performs row-major traversal and is ideal for read-only operations like summing, counting, and searching. Indexed for loops are required whenever you need to modify elements, access neighbors, track positions, or traverse in column-major order. On the AP exam, identifying the traversal order from nested loop structure and correctly tracing output are essential skills. Remember: the variable in the outer loop changes slowly, while the variable in the inner loop changes rapidly.