Array Traversal Patterns in DSA C++

Mental Model

Array traversal means visiting each element in the array one by one to read or change it.

Analogy: Imagine walking down a row of mailboxes, checking each one in order to find your mail or leave a note.

Index: 0   1   2   3   4
Array: [5]->[3]->[8]->[6]->[2]

Dry Run Walkthrough

Input: array: [5, 3, 8, 6, 2], traverse to print each element

Goal: Visit each element in order and print its value

Step 1: Start at index 0, read value 5

Index: 0↑ 1   2   3   4
Array: [5]->[3]->[8]->[6]->[2]

Why: We begin traversal from the first element

Step 2: Move to index 1, read value 3

Index: 0   1↑ 2   3   4
Array: [5]->[3]->[8]->[6]->[2]

Why: Next element in sequence to visit

Step 3: Move to index 2, read value 8

Index: 0   1   2↑ 3   4
Array: [5]->[3]->[8]->[6]->[2]

Why: Continue visiting elements in order

Step 4: Move to index 3, read value 6

Index: 0   1   2   3↑ 4
Array: [5]->[3]->[8]->[6]->[2]

Why: Keep moving forward through the array

Step 5: Move to index 4, read value 2

Index: 0   1   2   3   4↑
Array: [5]->[3]->[8]->[6]->[2]

Why: Last element to visit in the array

Result:

Index: 0   1   2   3   4↑
Array: [5]->[3]->[8]->[6]->[2]
Printed values: 5 3 8 6 2

Annotated Code

DSA C++

#include <iostream>
using namespace std;

void traverseArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " "; // print current element
    }
    cout << endl;
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    traverseArray(arr, size);
    return 0;
}

for (int i = 0; i < size; i++) {

loop through each index from start to end

cout << arr[i] << " ";

print the element at current index

Output

5 3 8 6 2 

Complexity Analysis

Time: O(n) because we visit each of the n elements once

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Compared to random access, traversal is simple and efficient; no extra data structures needed

Edge Cases

empty array

loop does not run, no output printed

DSA C++

for (int i = 0; i < size; i++) {

single element array

prints the single element correctly

DSA C++

for (int i = 0; i < size; i++) {

When to Use This Pattern

When you need to process or examine every item in a list or array, use array traversal to visit each element in order.

Common Mistakes

Mistake: Using <= instead of < in loop condition causing out-of-bounds access
Fix: Use i < size to ensure loop stops before exceeding array length

Summary

Visits each element in an array one by one.

Use when you want to read or update every item in a list.

Remember to start at index 0 and stop before the array length.

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