Why Array Traversal Patterns in DSA C++?

The Big Idea

What if you could never lose track while checking a list, no matter how long it is?

The Scenario

Imagine you have a list of your favorite songs written on paper. You want to find a specific song or play them all in order. Doing this by flipping pages one by one is like manually checking each song without a plan.

The Problem

Manually checking each item without a clear pattern is slow and confusing. You might skip songs, repeat some, or lose track of where you are. This makes finding or using items frustrating and error-prone.

The Solution

Array traversal patterns give you clear, simple ways to go through each item in a list. Whether you want to go from start to end, skip some items, or go backwards, these patterns help you do it quickly and without mistakes.

Before vs After

✗ Before

int arr[] = {1, 2, 3, 4, 5};
// Manually access each element
int first = arr[0];
int second = arr[1];
// ... and so on

✓ After

int arr[] = {1, 2, 3, 4, 5};
for (int index = 0; index < 5; index++) {
    std::cout << arr[index] << " ";
}

What It Enables

With array traversal patterns, you can easily process all items in a list, enabling tasks like searching, sorting, and transforming data efficiently.

Real Life Example

Think of scanning a grocery list to check off items as you shop. Using a clear pattern to look at each item ensures you don't miss anything or check the same item twice.

Key Takeaways

Manual checking is slow and error-prone.

Traversal patterns provide clear, repeatable ways to visit each item.

They make working with lists easier and more reliable.

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