Array Reversal Techniques in DSA C++

Mental Model

Reversing an array means flipping its order so the last element becomes first and the first becomes last.

Analogy: Imagine a row of books on a shelf; reversing the array is like taking the books from both ends and swapping them until you meet in the middle.

Index: 0   1   2   3   4
Array: 10 -> 20 -> 30 -> 40 -> 50

Dry Run Walkthrough

Input: array: [10, 20, 30, 40, 50]

Goal: Reverse the array so it becomes [50, 40, 30, 20, 10]

Step 1: Swap first element (10) with last element (50)

Index: 0   1   2   3   4
Array: 50 -> 20 -> 30 -> 40 -> 10

Why: Swap ends to start reversing the order

Step 2: Swap second element (20) with second last element (40)

Index: 0   1   2   3   4
Array: 50 -> 40 -> 30 -> 20 -> 10

Why: Continue swapping inward to reverse the array

Step 3: Middle element (30) remains as is because it is in the center

Index: 0   1   2   3   4
Array: 50 -> 40 -> 30 -> 20 -> 10

Why: No swap needed for middle element in odd-length array

Result:

Index: 0   1   2   3   4
Array: 50 -> 40 -> 30 -> 20 -> 10

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void reverseArray(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    while (left < right) {
        // Swap elements at left and right
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        // Move pointers inward
        left++;
        right--;
    }
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50};
    reverseArray(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

while (left < right) {

Continue swapping until pointers meet or cross

int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;

Swap elements at left and right positions

left++; right--;

Move pointers inward to next pair

Output

50 40 30 20 10 

Complexity Analysis

Time: O(n) because we swap pairs from both ends until the middle, touching each element once

Space: O(1) because swaps happen in place without extra storage

vs Alternative: Compared to creating a new reversed array (O(n) space), this method uses no extra space and is more efficient

Edge Cases

Empty array

No swaps happen, array remains empty

DSA C++

while (left < right) {

Single element array

No swaps happen, single element stays as is

DSA C++

while (left < right) {

Array with duplicate elements

Duplicates are swapped normally, order reversed correctly

DSA C++

int temp = arr[left];

When to Use This Pattern

When you need to reverse the order of elements in a list or array, use the two-pointer swap technique to efficiently reverse in place.

Common Mistakes

Mistake: Swapping elements without moving pointers inward, causing infinite loop
Fix: Increment left and decrement right pointers inside the loop after swapping

Mistake: Using <= instead of < in loop condition, causing unnecessary swap of middle element
Fix: Use while (left < right) to avoid swapping middle element twice

Summary

Reverses an array by swapping elements from both ends moving inward.

Use when you want to reverse the order of elements efficiently without extra space.

The key is to swap pairs from the outside moving toward the center until pointers meet.

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