Array Traversal Patterns in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Array Traversal

What is the output of the following C++ code that traverses a 2D array in a zigzag pattern?

DSA C++

int arr[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
for(int i=0; i<3; i++) {
  if(i % 2 == 0) {
    for(int j=0; j<3; j++) {
      std::cout << arr[i][j] << " ";
    }
  } else {
    for(int j=2; j>=0; j--) {
      std::cout << arr[i][j] << " ";
    }
  }
}

A 1 2 3 6 5 4 9 8 7

B 1 2 3 4 5 6 9 8 7

C 1 2 3 6 5 4 7 8 9

D 1 2 3 4 5 6 7 8 9

💡 Hint

Look at how the inner loop changes direction based on the row index.

The code prints rows in normal order for even rows and reversed order for odd rows, creating a zigzag pattern.

❓ Predict Output

intermediate

Output of Spiral Traversal of 3x3 Matrix

What is the output of this C++ code that prints elements of a 3x3 matrix in spiral order?

DSA C++

int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int top=0, bottom=2, left=0, right=2;
while(top <= bottom && left <= right) {
  for(int i=left; i<=right; i++) std::cout << matrix[top][i] << " ";
  top++;
  for(int i=top; i<=bottom; i++) std::cout << matrix[i][right] << " ";
  right--;
  if(top <= bottom) {
    for(int i=right; i>=left; i--) std::cout << matrix[bottom][i] << " ";
    bottom--;
  }
  if(left <= right) {
    for(int i=bottom; i>=top; i--) std::cout << matrix[i][left] << " ";
    left++;
  }
}

A 1 2 3 6 9 8 7 4 5

B 1 2 3 4 5 6 7 8 9

C 1 4 7 8 9 6 3 2 5

D 1 3 5 7 9 2 4 6 8

💡 Hint

Follow the boundaries top, bottom, left, right as they shrink inward.

The code prints the outer layer clockwise, then moves inward, producing a spiral order.

🧠 Conceptual

advanced

Understanding Time Complexity of Nested Array Traversal

If you have a nested loop traversing a 2D array of size n x n, what is the time complexity of the traversal?

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

💡 Hint

Think about how many elements are visited in total.

Traversing each element in an n x n matrix requires visiting n*n elements, so the time complexity is O(n^2).

🔧 Debug

advanced

Identify the Bug in Reverse Array Traversal Code

What error will this C++ code produce when trying to print an array in reverse?

DSA C++

int arr[5] = {10, 20, 30, 40, 50};
for(int i=4; i>=0; i--) {
  std::cout << arr[i] << " ";
}

A Compilation error: invalid loop condition

B Runtime error: out-of-bounds access

C Prints: 0 10 20 30 40 50

D Prints: 50 40 30 20 10 0

💡 Hint

Check the starting index and valid array indices.

The loop starts at i=5 but valid indices are 0 to 4, so arr[5] is out of bounds causing runtime error.

🚀 Application

expert

Find the Missing Number Using Array Traversal

Given an array of size n containing numbers from 1 to n+1 with one missing number, which approach correctly finds the missing number using traversal?

A Traverse array and multiply all elements, then divide by product of 1 to n+1

B Sort the array and check for the first missing number

C Use a hash set to track numbers and find missing one

D Sum all elements and subtract from total sum of 1 to n+1

💡 Hint

Think about a simple arithmetic property that helps find the missing number.

Summing all elements and subtracting from the expected total sum is efficient and uses simple traversal.

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