Array Reversal Techniques in DSA C++ - Execution Trace

Concept Flow - Array Reversal Techniques

Start with array

↓

Set left = 0, right = n-1

↓

Check if left < right?

No→Done

Yes↓

Swap array[left

↓

Increment left, Decrement right

↩Back to Check

Start with two pointers at the ends of the array, swap elements, move pointers inward until they meet.

Execution Sample

DSA C++

int arr[] = {1, 2, 3, 4, 5};
int left = 0, right = 4;
while (left < right) {
  std::swap(arr[left], arr[right]);
  left++;
  right--;
}

This code reverses the array by swapping elements from the ends moving inward.

Execution Table

Step	Operation	Left Index	Right Index	Array State	Pointer Changes
1	Initialize pointers	0	4	[1, 2, 3, 4, 5]	left=0, right=4
2	Check condition left < right	0	4	[1, 2, 3, 4, 5]	Condition True
3	Swap arr[left] and arr[right]	0	4	[5, 2, 3, 4, 1]	Swapped arr[0] and arr[4]
4	Increment left, Decrement right	1	3	[5, 2, 3, 4, 1]	left=1, right=3
5	Check condition left < right	1	3	[5, 2, 3, 4, 1]	Condition True
6	Swap arr[left] and arr[right]	1	3	[5, 4, 3, 2, 1]	Swapped arr[1] and arr[3]
7	Increment left, Decrement right	2	2	[5, 4, 3, 2, 1]	left=2, right=2
8	Check condition left < right	2	2	[5, 4, 3, 2, 1]	Condition False
9	End loop	2	2	[5, 4, 3, 2, 1]	Array reversed

💡 left equals right (2 == 2), condition left < right is false, loop ends

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 7	Final
left	0	0	1	1	2	2
right	4	4	3	3	2	2
arr	[1, 2, 3, 4, 5]	[5, 2, 3, 4, 1]	[5, 2, 3, 4, 1]	[5, 4, 3, 2, 1]	[5, 4, 3, 2, 1]	[5, 4, 3, 2, 1]

Key Moments - 3 Insights

Why do we stop swapping when left equals right?

Because when left equals right, it means we reached the middle element in an odd-length array, which does not need swapping. See execution_table step 8 where condition left < right becomes false.

Why do we swap arr[left] and arr[right] before moving the pointers?

Swapping first ensures the elements at the ends are exchanged before pointers move inward. If pointers moved first, we would skip swapping the first pair. Refer to execution_table steps 3 and 6.

What happens if the array is empty or has one element?

The condition left < right is false immediately, so no swaps occur and the array remains unchanged. This is implied by the exit condition in execution_table step 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 6?

A [1, 2, 3, 4, 5]

B [5, 2, 3, 4, 1]

C [5, 4, 3, 2, 1]

D [1, 4, 3, 2, 5]

💡 Hint

Check the 'Array State' column at step 6 in the execution_table.

At which step does the condition left < right become false?

A Step 8

B Step 7

C Step 9

D Step 6

💡 Hint

Look at the 'Pointer Changes' and 'Operation' columns in execution_table steps 7 and 8.

If the array length was 4 instead of 5, how many swaps would occur?

A 1

B 2

C 3

D 4

💡 Hint

Think about how many pairs of elements are swapped when left < right for an even length array.

Concept Snapshot

Array Reversal Technique:
- Use two pointers: left at start, right at end
- While left < right:
  - Swap elements at left and right
  - Move left forward, right backward
- Stops when pointers meet or cross
- Works for arrays of any size

Full Transcript

This visualization shows how to reverse an array by swapping elements from the ends moving inward. We start with two pointers, left at index 0 and right at the last index. While left is less than right, we swap the elements at these positions, then move left forward and right backward. This continues until the pointers meet or cross, meaning the array is reversed. The execution table tracks each step, showing the array state and pointer positions. Key moments clarify why we stop when pointers meet and why swapping happens before moving pointers. The quiz tests understanding of array states and loop conditions during reversal.

Practice

1. What does reversing an array mean in simple terms?

easy

A. Changing the order of elements so the last becomes first and first becomes last

B. Sorting the array in ascending order

C. Removing duplicate elements from the array

D. Adding new elements at the end of the array

Solution

1. Step 1: Understand the meaning of reversal

   Reversing means flipping the order of elements so the last element comes first and the first element goes last.

2. Step 2: Compare with other options

   Sorting arranges elements by value, removing duplicates deletes repeated items, adding elements increases size. None of these change order like reversal.

3. Final Answer:

   Changing the order of elements so the last becomes first and first becomes last -> Option A

4. Quick Check:

   Reversal = Flip order [OK]

Hint: Reversal flips order, not sorting or removing [OK]

Common Mistakes:

• Confusing reversal with sorting
• Thinking reversal removes elements
• Mixing reversal with adding elements

2. Which of the following C++ code snippets correctly reverses an array arr of size n using a for loop?

easy

A. for(int i = 0; i < n; i++) { arr[i] = arr[i]; }

B. for(int i = 0; i < n; i++) { arr[i] = arr[n - i]; }

C. for(int i = 0; i < n / 2; i++) { std::swap(arr[i], arr[n - i - 1]); }

D. for(int i = 0; i < n; i++) { arr[i] = arr[i + 1]; }

Solution

1. Step 1: Analyze the correct reversal loop

   The loop swaps elements from start and end moving towards the center, stopping at half the array size.

2. Step 2: Check other options for errors

   A does nothing, for(int i = 0; i < n; i++) { arr[i] = arr[n - i]; } accesses out-of-bound index (arr[n - i]), C shifts elements incorrectly.

3. Final Answer:

   for(int i = 0; i < n / 2; i++) { std::swap(arr[i], arr[n - i - 1]); } -> Option C

4. Quick Check:

   Swap pairs from ends to middle [OK]

Hint: Swap pairs from ends to middle to reverse [OK]

Common Mistakes:

• Accessing out-of-bound indices
• Not stopping loop at half the array
• Overwriting elements without swapping

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

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

medium

A. 5 4 3 2 1

B. 1 2 3 4 5

C. 5 2 3 4 1

D. 4 3 2 1 5

Solution

1. Step 1: Trace the swapping loop

   Swaps arr[0] with arr[4], arr[1] with arr[3]. After swaps, arr = {5,4,3,2,1}.

2. Step 2: Print the array elements

   The loop prints all elements in order: 5 4 3 2 1.

3. Final Answer:

   5 4 3 2 1 -> Option A

4. Quick Check:

   Reversed array prints 5 4 3 2 1 [OK]

Hint: Swapping pairs reverses array elements [OK]

Common Mistakes:

• Not swapping correctly
• Loop running too many times
• Printing before reversal

4. Identify the error in the following code that attempts to reverse an array arr of size n:

for(int i = 0; i <= n / 2; i++) {
  int temp = arr[i];
  arr[i] = arr[n - i - 1];
  arr[n - i - 1] = temp;
}

medium

A. No error; the code correctly reverses the array

B. The swap logic is incorrect; it should swap arr[i] with arr[i+1]

C. The loop should run from i = 1 to n / 2 instead of 0

D. The loop condition should be 'i < n / 2' to avoid swapping the middle element twice

Solution

1. Step 1: Analyze the loop condition

   The loop runs while i <= n/2, which includes the middle element when n is odd.

2. Step 2: Understand the effect of swapping middle element twice

   Swapping the middle element with itself is unnecessary and can cause incorrect behavior or redundant operation.

3. Final Answer:

   The loop condition should be 'i < n / 2' to avoid swapping the middle element twice -> Option D

4. Quick Check:

   Loop must stop before middle index [OK]

Hint: Use 'i < n/2' to avoid double swapping middle element [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Swapping wrong elements
• Starting loop from 1 instead of 0

5. Given a 2D array (matrix) of size m x n, which approach correctly reverses each row individually in C++?

hard

A. Swap elements column-wise from first to last column for all rows simultaneously

B. Use a nested loop: for each row, swap elements from start to end using two pointers

C. Transpose the matrix and then reverse the entire matrix as a 1D array

D. Sort each row in descending order to reverse it

Solution

1. Step 1: Understand reversing each row

   Reversing each row means flipping elements in that row only, not affecting other rows.

2. Step 2: Identify correct method

   Using two pointers per row to swap elements from start and end is the correct approach.

3. Step 3: Check incorrect options

   Swapping column-wise mixes rows, transposing changes structure, sorting changes order by value, not position.

4. Final Answer:

   Use a nested loop: for each row, swap elements from start to end using two pointers -> Option B

5. Quick Check:

   Reverse rows by swapping pairs inside each row [OK]

Hint: Reverse each row with two-pointer swaps inside nested loop [OK]

Common Mistakes:

• Trying to reverse columns instead of rows
• Using sorting instead of reversing
• Transposing matrix instead of reversing rows