Array Traversal Patterns in DSA C++ - Execution Trace

Concept Flow - Array Traversal Patterns

Start at index 0

↓

Check: index < array length?

No→End traversal

Yes↓

Access element at index

↓

Process element

↓

Increment index

↩Back to Check

Start from the first element, check if the index is within bounds, access and process the element, then move to the next index until all elements are visited.

Execution Sample

DSA C++

#include <iostream>
using namespace std;

int main() {
    int arr[] = {10, 20, 30, 40};
    int n = 4;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

This code prints each element of the array one by one from start to end.

Execution Table

Step	Operation	Index (i)	Condition (i < n)	Element Accessed	Output	Action
1	Initialize i	0	0 < 4 = True	arr[0] = 10	10	Print element, increment i
2	Loop iteration	1	1 < 4 = True	arr[1] = 20	20	Print element, increment i
3	Loop iteration	2	2 < 4 = True	arr[2] = 30	30	Print element, increment i
4	Loop iteration	3	3 < 4 = True	arr[3] = 40	40	Print element, increment i
5	Loop iteration	4	4 < 4 = False	-	-	Exit loop

💡 Index i reaches 4, condition i < n becomes false, loop ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	-	0	1	2	3	4
Output	""	"10 "	"10 20 "	"10 20 30 "	"10 20 30 40 "	"10 20 30 40 "

Key Moments - 3 Insights

Why does the loop stop when i equals the array length?

Because the condition i < n becomes false at i = 4 (array length), so the loop exits as shown in execution_table row 5.

Why do we start indexing from 0 instead of 1?

Arrays in C++ start at index 0, so the first element is at arr[0], as shown in execution_table row 1.

What happens if we try to access arr[i] when i equals n?

Accessing arr[n] is out of bounds and causes undefined behavior; the loop prevents this by stopping before i reaches n, as shown in the exit condition.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i at Step 3?

A 1

B 3

C 2

D 4

💡 Hint

Check the 'Index (i)' column at Step 3 in the execution_table.

At which step does the loop condition become false?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Condition (i < n)' column where it changes to false.

If the array length n was 3 instead of 4, how many times would the loop run?

A 3 times

B 2 times

C 4 times

D 1 time

💡 Hint

Refer to the exit_note and how the loop stops when i equals n.

Concept Snapshot

Array Traversal Pattern:
- Start index at 0
- Loop while index < array length
- Access element at current index
- Process element (e.g., print)
- Increment index
- Stop when index reaches length

Full Transcript

Array traversal means visiting each element in order from the first to the last. We start at index zero and check if the index is less than the array length. If yes, we access and process the element, then move to the next index. This repeats until the index equals the array length, where the loop stops to avoid out-of-bounds access. This pattern is common in C++ and many other languages.

Practice

1. What does the following loop do when traversing an array arr of size n?

for (int i = 0; i < n; i++) { /* code */ }

easy

A. It visits each element from the first to the last in order.

B. It visits elements in reverse order from last to first.

C. It visits only even-indexed elements.

D. It skips the first element and visits the rest.

Solution

1. Step 1: Understand the loop variable and range

   The loop variable i starts at 0 and increases by 1 until it reaches n-1.

2. Step 2: Determine the traversal order

   Since i increments from 0 to n-1, the loop visits elements from the first to the last in order.

3. Final Answer:

   It visits each element from the first to the last in order. -> Option A

4. Quick Check:

   Forward traversal = It visits each element from the first to the last in order. [OK]

Hint: Loop from 0 to n-1 means forward traversal [OK]

Common Mistakes:

• Thinking it visits elements in reverse order
• Assuming it skips elements
• Confusing index start with 1 instead of 0

2. Which of the following is the correct syntax to traverse an array arr of size n backwards in C++?

easy

A. for (int i = n-1; i >= 0; i--) { /* code */ }

B. for (int i = 0; i < n; i++) { /* code */ }

C. for (int i = n; i > 0; i--) { /* code */ }

D. for (int i = n-1; i <= 0; i--) { /* code */ }

Solution

1. Step 1: Identify correct start and end conditions

   To traverse backwards, start at n-1 (last index) and go down to 0.

2. Step 2: Check loop condition and decrement

   The loop must continue while i >= 0 and decrement i-- each time.

3. Final Answer:

   for (int i = n-1; i >= 0; i--) { /* code */ } -> Option A

4. Quick Check:

   Backward loop: start=n-1, end=0, decrement [OK]

Hint: Backward loop starts at n-1 and decrements to 0 [OK]

Common Mistakes:

• Using i <= 0 instead of i >= 0
• Starting at n instead of n-1
• Incrementing instead of decrementing

3. What is the output of the following C++ code?

int arr[] = {10, 20, 30, 40, 50};
int n = 5;
for (int i = 1; i < n; i += 2) {
    std::cout << arr[i] << " ";
}

medium

A. 10 30 50

B. 20 40 50

C. 10 20 30 40 50

D. 20 40

Solution

1. Step 1: Identify loop indices visited

   The loop starts at i=1 and increments by 2: i=1, 3, then stops before 5.

2. Step 2: Find elements at these indices

   arr[1] = 20, arr[3] = 40. These are printed separated by space.

3. Final Answer:

   20 40 -> Option D

4. Quick Check:

   Indices 1 and 3 values = 20 40 [OK]

Hint: Step by 2 from 1 visits odd indices [OK]

Common Mistakes:

• Including index 5 which is out of bounds
• Starting from 0 instead of 1
• Printing all elements instead of skipping

4. Find the error in the following code snippet that tries to print all elements of an array arr of size n:

for (int i = 0; i <= n; i++) {
    std::cout << arr[i] << " ";
}

medium

A. The loop should increment i-- instead of i++.

B. The loop condition should be i < n instead of i <= n.

C. The array index should be i-1 inside the loop.

D. The loop variable i should start from 1.

Solution

1. Step 1: Analyze loop boundary condition

   The loop runs while i <= n, so it accesses arr[n] which is out of bounds.

2. Step 2: Correct the loop condition

   Change condition to i < n to access valid indices 0 to n-1.

3. Final Answer:

   The loop condition should be i < n instead of i <= n. -> Option B

4. Quick Check:

   Array indices 0 to n-1 valid, not n [OK]

Hint: Array indices go from 0 to n-1, not n [OK]

Common Mistakes:

• Using <= n causes out-of-bounds access
• Starting loop at 1 misses first element
• Decrementing i in a forward loop

5. Given an array arr of size n, which code snippet correctly prints elements at even indices in reverse order?

hard

A. for (int i = n-1; i >= 0; i -= 2) { std::cout << arr[i] << " "; }

B. for (int i = 0; i < n; i += 2) { std::cout << arr[i] << " "; }

C. for (int i = (n % 2 == 0 ? n-2 : n-1); i >= 0; i -= 2) { std::cout << arr[i] << " "; }

D. for (int i = n-2; i <= 0; i -= 2) { std::cout << arr[i] << " "; }

Solution

1. Step 1: Determine the highest even index to start

   If n is even, highest even index is n-2; if odd, it's n-1.

2. Step 2: Loop backwards by 2 from that index down to 0

   The loop decrements i by 2 each time, printing even indices in reverse order.

3. Final Answer:

   for (int i = (n % 2 == 0 ? n-2 : n-1); i >= 0; i -= 2) { std::cout << arr[i] << " "; } -> Option C

4. Quick Check:

   Start at highest even index, decrement by 2 [OK]

Hint: Start at highest even index, decrement by 2 [OK]

Common Mistakes:

• Starting at n-1 always (may be odd index)
• Loop condition incorrect (i <= 0 instead of i >= 0)
• Incrementing instead of decrementing in reverse