Array Traversal Patterns in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is array traversal?

Array traversal means visiting each element in an array one by one, usually from the first element to the last.

beginner

How do you traverse an array forwards in C++?

Use a for loop starting from index 0 up to the last index, accessing each element in order.

beginner

What is reverse traversal of an array?

Reverse traversal means visiting array elements starting from the last element to the first.

intermediate

Why might you use a step size greater than 1 in array traversal?

Using a step size greater than 1 lets you skip elements, for example, to access every second element.

intermediate

What is a common pattern to traverse a 2D array?

Use nested loops: the outer loop for rows and the inner loop for columns to visit each element.

Which loop is typically used for array traversal in C++?

A while loop

B do-while loop

C for loop

D switch statement

The for loop is most commonly used because it clearly controls the index from start to end.

What is the index of the last element in an array of size n?

A n - 1

B n

C 0

D 1

Array indices start at 0, so the last element is at index n - 1.

How do you traverse an array backwards?

A Start from index n-1 to 0

B Start from index 0 to n-1

C Start from index 1 to n

D Start from index n to 1

Reverse traversal starts from the last index (n-1) down to 0.

What does a step size of 2 in traversal do?

A Visits every element

B Stops traversal early

C Visits elements in reverse

D Skips every other element

A step size of 2 means you move two indices at a time, skipping one element each time.

Which structure is best to traverse a 2D array?

A Single for loop

B Nested for loops

C While loop only

D Switch statement

Nested for loops let you access rows and columns systematically.

Explain how to traverse a one-dimensional array forwards and backwards.

Think about how the index changes in each case.

Describe the pattern to traverse a two-dimensional array and why nested loops are used.

Imagine walking through a grid row by row.

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