Array Tracing & Mystery Strategy

In a nutshell

Tracing array code by hand is the most important quiz and exam skill of this unit. It shows up on Quiz 6, Midterm 2, and the Final. Every “what is a at the end?” problem you see between now and the end of the quarter is the same shape: a short loop that uses indices and writes to slots, and you have to predict the final array.

There is exactly one strategy that works:

1. Get out a piece of paper and a pencil. The trace table is your answer key. You cannot build it in your head.
2. Read each indexed expression as a tiny three-step calculation: substitute the variable, simplify the arithmetic, look up the slot.
3. Treat the array as live. Every line that writes to a[i] updates the array right then. The next line reads from the new picture, not from the original input.

That’s the whole technique. Below, every step is broken down slowly, with the mental model behind it, then three full walkthroughs, then a named inventory of every “trap” the mystery genre is engineered to catch you on.

After this lesson, you will be able to:

• Picture an array clearly enough that the syntax stops getting in the way.
• Evaluate any indexed expression by hand: a[i], a[i + 1], a[i - 1], a[a.length - 1 - i].
• Build a trace table for a one-loop array program in three minutes, without skipping rows.
• Name the trap a problem is testing on sight, and apply the right counter-strategy.

A mental model: cubbies with number stickers

Picture a row of identical cubbies on a wall. Each cubby has a small sticker on the front with a number: 0, 1, 2, 3, 4. Inside each cubby is one item.

The cubby’s number sticker never changes. The item inside can change at any time.

cubby:    0     1     2     3     4
        ┌───┬─────┬───┬─────┬───┐
        │ 7 │  2  │ 9 │  4  │ 5 │
        └───┴─────┴───┴─────┴───┘

Two pieces of vocabulary you must keep separate:

• i is a number sticker. It tells you which cubby you’re looking at.
• a[i] is the item inside that cubby. It’s whatever is in there right now.

Almost every array bug comes from confusing these two. We’ll come back to this in a minute.

The other piece: cubbies can hold the same kind of thing — all ints in an int[], all Strings in a String[] — and the number of cubbies is fixed when you build the row. You can’t add a new cubby on the end. To make the row longer, you build a new row.

Why you can’t trace in your head

Every term, students try to do array mysteries in their head and lose easy points. Here is exactly what goes wrong, so you’ll recognize it when it tries to happen to you.

• You forget the previous iteration. Once i reaches 3, the value of a[1] from the second iteration has fallen out of your working memory. The trace table remembers it for you so your brain doesn’t have to.
• You substitute wrong. a[i + 1] when i = 2 is not a[i + 1] — it’s a[3]. Doing that substitution silently in your head is where off-by-one errors sneak in. Writing it on paper makes the substitution a visible step, and your eye catches the error.
• You read i when you meant a[i] (or the other way around). They look almost the same. They mean opposite things. The table forces you to keep them in separate columns where you can’t blur them together.

The rule for the rest of this lesson: paper first, always. It will feel slow on problem one and fast by problem three.

Step 1: Read indexed expressions like algebra

The expression a[i + 1] is not one thing. It’s three steps in a row, like a tiny algebra problem.

1. Substitute. Replace the variable inside the brackets with its current value.
2. Simplify. Do the arithmetic.
3. Look up. Read the value at that index from the array.

You’ll be tempted to skip steps 2 and 3 once you “feel comfortable.” Don’t. Skipping is exactly where the bug hides.

Worked example

Suppose:

int[] a = {7, 2, 9, 4, 5};   // indices 0..4
int i = 2;

Evaluate a[i + 1]. On paper:

That’s how every indexed expression is read. Slow it down, write each step.

Five patterns you will see again and again

Same array, a = {7, 2, 9, 4, 5}, but now i = 1:

Three of these patterns are worth knowing on sight, because nearly every mystery problem uses one of them.

a[i - 1] — the previous neighbor. The cubby just to the left. Trap: when i = 0, this is a[-1], which crashes. So loops that use a[i - 1] almost always start at i = 1, not i = 0.

a[i + 1] — the next neighbor. The cubby just to the right. Trap: when i = a.length - 1, this is a[a.length], which crashes. So loops that use a[i + 1] almost always stop at i < a.length - 1, not i < a.length.

a[a.length - 1 - i] — the mirror. When i = 0 this is the last index. When i = a.length - 1 this is 0. The pattern walks pairs from the outside in: a[0] and the last cubby, a[1] and the second-to-last, and so on.

i vs a[i]: the most common confusion in the unit

Ask yourself, every single time you read a condition: is this looking at the cubby’s number, or at what’s inside the cubby?

• i % 2 == 0 asks: is the cubby’s number sticker even? It fires at indices 0, 2, 4, ... regardless of what’s inside.
• a[i] % 2 == 0 asks: is the item inside the cubby an even number? It fires only where the data happens to be even.

Same array, opposite results. Underline which variable the condition is testing before you build the table.

Check your understanding. Given int[] a = {3, 6, 5, 2, 7}, on which indices i does each condition fire as the loop walks i = 0, 1, 2, 3, 4?

A. i % 2 == 0 B. a[i] % 2 == 0

Reveal answer

A fires at indices 0, 2, 4 (the even cubby numbers). The values stored in those cubbies happen to be 3, 5, 7, but the condition does not look at them.

B fires at indices 1, 3 (the cubbies whose contents are even — 6 and 2).

The two conditions look identical and produce different sets of “fire” rows. This is the most common parity-mystery trap, and it shows up at least once on every Mystery quiz.

Step 2: Build a trace table

Once you can evaluate one indexed expression, the rest is bookkeeping. The standard format is a table with one row per iteration of the loop and one column per moving part.

What to include in the columns (in order):

• The index variable, usually i.
• Any value the loop reads — a[i], and often a[i - 1] and a[i + 1] if the body uses neighbors.
• The condition’s result — yes / no, or true / false.
• The slot being written and the new value going into it.
• The contents of a after the iteration. This last column is critical — it’s your live record of the array.

Worked example

Trace this on int[] a = {3, 6, 5, 2, 7}:

for (int i = 0; i < a.length; i++) {
    if (i % 2 == 0) {
        a[i] = a[i] + 10;
    }
}

Final answer: a is {13, 6, 15, 2, 17}. Five rows, about two minutes on paper.

Three rules to keep the table honest

1. One row per iteration. Every iteration. Even rows where the condition fires no and nothing changes belong in the table. They’re part of the proof, and quizzes occasionally ask “how many iterations of the body actually ran?” — which you can answer instantly from a complete table.

2. Add columns until the table is unambiguous. If the body uses a[i - 1], give it a column. If it uses two index variables, give each its own column. Do not recompute the same expression twice in your head.

3. Update the “a” column every row. That column is your current picture of the array. The next row reads from it, not from the input on the problem sheet. (More on this in Step 3.)

Step 3: The array is live

This is the rule that defeats more students than any other rule in the unit. Read it carefully.

When a loop writes to a slot, the array changes right then. The next iteration — and the next read on the very next line — sees the new value, not the original.

The mental model: think of the array as a whiteboard. Each line of code that writes to a slot picks up the marker, erases that slot, and writes the new value. The next line reads from the whiteboard’s current state, not from a photo of what it looked like before the loop started.

Tiny example, no loop at all

int[] a = {3, 5, 8};
a[0] = a[0] + 1;   // a is now {4, 5, 8}
a[1] = a[0] + 1;   // reads the NEW a[0] = 4. So a[1] = 5.
                   //   a is now {4, 5, 8}.
a[2] = a[1] + 1;   // reads the latest a[1]. a[2] = 6.
                   //   a is now {4, 5, 6}.

Read line 3 carefully. a[1] = a[0] + 1; — the right-hand side reads a[0] after line 2 wrote 4 there. It does not read the original 3. Same for line 4: it reads the latest a[1], which line 3 just wrote.

That’s the whole rule. Now apply it inside a loop, where the cascade gets trickier.

Worked example with cascading reads

Trace mystery(a) on int[] a = {4, 7, 4, 2, 10, 9}:

public static void mystery(int[] a) {
    for (int i = 1; i < a.length - 1; i++) {
        a[i] = a[i + 1] + a[i - 1];
    }
}

The bound i = 1 to i < a.length - 1 (which is < 5) runs i = 1, 2, 3, 4. The first cubby (a[0]) and the last cubby (a[5]) never change.

The body uses both neighbors, so the table needs columns for a[i - 1] and a[i + 1]. Pay attention to the “(live)” annotation on the a[i - 1] column — it’s a reminder that this read picks up whatever the previous row just wrote.

Read row 2 carefully. a[i - 1] is a[1]. We just wrote 8 there in row 1. So a[i - 1] = 8, not the original 7. If you used the input array’s 7 here, you’d get 2 + 7 = 9 for the new a[2], and from there every later row would be wrong.

The cascading “live” reads are the entire reason this kind of problem is hard. The trace table is what makes it tractable.

Walkthrough 1: a parity puzzle

Take this slowly. Trace it on paper before you read the answer.

Input: int[] a = {3, 6, 5, 2, 7}. Code:

for (int i = 0; i < a.length; i++) {
    if (a[i] % 2 == 0) {
        a[i] = a[i] + 10;
    }
}

This problem is the same shape as the worked example earlier in Step 2, but the condition tests a[i] % 2 == 0 (the value’s parity), not i % 2 == 0 (the index’s parity). One word changed. The answer is completely different.

Start the table. Underline the condition first to make sure you’re testing the right thing: a[i] % 2 == 0 — value parity. Now build columns for i, a[i], the condition value, fire?, a[i] after, and the live a.

Final array: {3, 16, 5, 12, 7}.

Look at the side-by-side: same input, two conditions that differ by one word, two completely different answers ({13, 6, 15, 2, 17} vs {3, 16, 5, 12, 7}). The graders are betting some students will read i % 2 and trace a[i] % 2, or vice versa. They’ll be right about that bet for some students. Don’t be one.

Walkthrough 2: a live cascade

Input: int[] a = {1, 5, 0, 0, 5, 0}. Code:

public static void mystery(int[] a) {
    for (int i = 1; i < a.length - 1; i++) {
        a[i] = a[i + 1] + a[i - 1];
    }
}

Bounds: i = 1 to i < 5, so the loop runs for i = 1, 2, 3, 4. The first and last cubbies (a[0] = 1, a[5] = 0) never change. The body reads both neighbors.

Build the table. Critical: the “a after” column is your live picture, and the next row’s a[i - 1] reads from it.

Final: {1, 1, 1, 6, 6, 0}.

Check row 4. a[i - 1] is a[3]. The input had 0 there, but row 3 just wrote 6. We use the live 6, not the original 0. That single live-read is what pushes a[4] from 5 (the original input) to 6 (the cascade result).

If your answer differs from {1, 1, 1, 6, 6, 0} by even one slot, find the row where you read the original instead of the live value. The bug is almost always there.

The named trap inventory

Mystery problems are not random. Each one is engineered to test a specific misconception. Once you can name the trap, you know what to look for and how to disarm it.

Read every entry. The “shape in code” column tells you what the problem looks like; the “what students do” column is the wrong move; the “fix” column is the correct counter.

Index & bounds traps

i vs a[i] traps

Live-array traps

Neighbor & boundary traps

Construction & initialization traps

How to use this inventory

When you read a mystery problem on a quiz, your first move (after writing i = and starting the table) should be to ask: which trap is this? Skim the trap list and find the one whose “shape in code” matches what you see. Then apply the fix while you trace.

Most problems combine two or three traps. A typical Quiz-6-shape problem reads roughly: “loop walks an array, body uses neighbor reads, condition tests value parity, array is live.” That’s three traps stacked: Slot-vs-Value, Live-Cascade, Negative-Index. Naming them gives you something concrete to verify on every row.

Practice on real problems

The technique only sticks if you do it on problems you haven’t seen before, on paper, with the trace table, every time.

• Quiz 6 prep — code.jdoner.me/cat/cscd210-s26-w6-quiz-prep. Worked-example problems matched to the quiz format. Trace each one on paper first. Only then check the answer.
• CodeStepByStep — Array tracing problem set 14780. A larger pool of mystery problems. Same rule: paper first.

When you check your answer and it’s wrong, don’t just re-read the code. Find the row in your trace table where you made the mistake, and re-do that row carefully. Then name the trap that bit you. The bug is almost always one of the named traps above.

Wrap up

• Tracing array code is a paper skill. Get out paper before you read the problem.
• Indexed expressions: substitute → simplify → look up. Don’t skip steps.
• Trace table: one row per iteration, one column per moving part, one final “a” column you update every row.
• The array is live. After every write, the next read sees the new value.
• i and a[i] look the same on a fast read and mean opposite things.
• Mystery problems test specific named traps. Recognize the trap, apply the fix.

This skill is on Quiz 6, Midterm 2, and the Final. The students who score well on tracing are the ones who built the habit of writing the table every time, even when they thought they didn’t need to.