Array Reversal Techniques in DSA C# - Time & Space Complexity

Time Complexity: Array Reversal Techniques

O(n)

Understanding Time Complexity

We want to understand how the time taken to reverse an array changes as the array gets bigger.

How does the number of steps grow when we reverse more elements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void ReverseArray(int[] arr)
{
    int start = 0;
    int end = arr.Length - 1;
    while (start < end)
    {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
    

This code reverses the elements of an array by swapping pairs from the start and end moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Swapping two elements in the array.
• How many times: About half the length of the array (n/2 times).

How Execution Grows With Input

As the array size grows, the number of swaps grows roughly half as fast.

Input Size (n)	Approx. Operations (Swaps)
10	5
100	50
1000	500

Pattern observation: The operations grow linearly with input size, just half as many swaps as elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to reverse the array grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Reversing an array takes constant time because we just swap elements."

[OK] Correct: Each swap is a step, and the number of swaps grows with the array size, so time grows linearly, not constant.

Interview Connect

Understanding this helps you explain how simple operations scale and shows you can analyze loops clearly, a key skill in interviews.

Self-Check

"What if we used recursion to reverse the array instead of a loop? How would the time complexity change?"

Practice

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

easy

A. Removing duplicate elements from the array

B. Sorting the array in ascending order

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

D. Adding new elements at the end of the array

Solution

1. Step 1: Understand array order

   An array has elements arranged from first to last in a sequence.

2. Step 2: Define reversal

   Reversing means swapping elements so the last element moves to the front and the first moves to the end, flipping the order.

3. Final Answer:

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

4. Quick Check:

   Reversal = Flip order [OK]

Hint: Reversal flips the array order front to back [OK]

Common Mistakes:

• Confusing reversal with sorting
• Thinking reversal removes elements
• Assuming reversal adds elements

2. Which of the following is the correct syntax to reverse an array named arr in C# using built-in methods?

easy

A. Array.Reverse(arr);

B. arr.Reverse();

C. reverse(arr);

D. arr.reverse();

Solution

1. Step 1: Identify C# array reversal method

   C# provides a static method Array.Reverse() to reverse arrays in place.

2. Step 2: Check syntax correctness

   The correct syntax calls Array.Reverse(arr); with capital 'A' and 'R' and no return value.

3. Final Answer:

   Array.Reverse(arr); -> Option A

4. Quick Check:

   Use Array.Reverse(arr) in C# [OK]

Hint: Use Array.Reverse(arr) to reverse arrays in C# [OK]

Common Mistakes:

• Using lowercase method names
• Calling reverse as instance method on array
• Using non-existent reverse functions

3. What will be the output of the following C# code?

int[] arr = {1, 2, 3, 4, 5};
Array.Reverse(arr);
Console.WriteLine(string.Join(", ", arr));

medium

A. 1, 2, 3, 4, 5

B. 5, 2, 3, 4, 1

C. Syntax Error

D. 5, 4, 3, 2, 1

Solution

1. Step 1: Understand Array.Reverse effect

   The method reverses the array elements in place, so the order flips.

2. Step 2: Trace the output

   Original array: 1, 2, 3, 4, 5 becomes 5, 4, 3, 2, 1 after reversal.

3. Final Answer:

   5, 4, 3, 2, 1 -> Option D

4. Quick Check:

   Reversed array prints 5 to 1 [OK]

Hint: Reversal flips array order exactly [OK]

Common Mistakes:

• Assuming reversal sorts the array
• Expecting original order after reversal
• Confusing output format

4. Identify the error in the following C# code that attempts to reverse an array:

int[] arr = {10, 20, 30};
arr.Reverse();
Console.WriteLine(string.Join(", ", arr));

medium

A. arr.Reverse() does not reverse the array in place

B. Array must be converted to list before reversing

C. Console.WriteLine syntax is incorrect

D. No error, code works fine

Solution

1. Step 1: Check arr.Reverse() method

   In C#, arr.Reverse() returns a reversed sequence but does not change the original array.

2. Step 2: Understand effect on original array

   The original array remains unchanged, so printing it shows original order, not reversed.

3. Final Answer:

   arr.Reverse() does not reverse the array in place -> Option A

4. Quick Check:

   arr.Reverse() returns reversed IEnumerable, no in-place change [OK]

Hint: Array.Reverse(arr) reverses in place; arr.Reverse() does not [OK]

Common Mistakes:

• Assuming arr.Reverse() changes original array
• Confusing LINQ Reverse with Array.Reverse
• Ignoring return value of arr.Reverse()

5. Given an integer array arr with an odd number of elements, which approach correctly reverses the array in place without using built-in methods?

hard

A. Create a new array and copy elements from end to start, then assign back to original array

B. Use two pointers, one at start and one at end, swap elements and move pointers towards center until they meet

C. Sort the array in descending order to reverse it

D. Remove the middle element and reverse the rest of the array

Solution

1. Step 1: Understand in-place reversal with two pointers

   Start with one pointer at the first element and another at the last element, swap their values.

2. Step 2: Move pointers towards center and swap

   Increment the start pointer and decrement the end pointer, continue swapping until pointers meet or cross.

3. Final Answer:

   Use two pointers, one at start and one at end, swap elements and move pointers towards center until they meet -> Option B

4. Quick Check:

   Two-pointer swap reverses array in place [OK]

Hint: Swap start and end elements moving inward [OK]

Common Mistakes:

• Using sorting instead of reversal
• Creating extra arrays unnecessarily
• Removing elements instead of swapping