Reverse a char[] in place in O(n) time and O(1) space
Implement Reverse(s) that reverses the char[] IN PLACE — modify the same array, return nothing. Requirements: O(n) time and O(1) extra space — no second array, no Array.Reverse, no LINQ. A single-element or empty array must come out unchanged.
public static void Reverse(char[] s)
{
// your code here
}Write the implementation.
Two indices l = 0 and r = s.Length - 1. While l < r, swap s[l] and s[r] (a tuple swap (s[l], s[r]) = (s[r], s[l])), then l++ and r--. The loop ends when they cross, reversing in place. O(n) time, O(1) extra space.
- ✗Looping all the way to the end and swapping twice, which restores the original order
- ✗Allocating a second array, violating the O(1) extra-space requirement
- ✗Returning a new value instead of mutating the passed-in array in place
- →Why must the loop stop at
l < rand not run to the end? - →How would surrogate pairs (emoji) break a naive per-
charreversal?
Task
Reverse the character array in place, without allocating a second array.
public static void Reverse(char[] s)
{
int l = 0, r = s.Length - 1;
while (l < r)
{
(s[l], s[r]) = (s[r], s[l]); // tuple swap, in place
l++;
r--;
}
}How it works
Two indices start at the ends of the array. On each step we swap the mirrored pair s[l] and s[r] with a tuple swap — it needs no temporary variable. Then l moves right and r moves left.
The key detail is the l < r condition: the loop stops as soon as the indices meet or cross. If it ran to the end, every pair would be swapped twice and the array would return to its original order.
Each pair is swapped exactly once, giving O(n) time and O(1) space. An empty or single-element array immediately fails the l < r condition and is left unchanged.
