Problem Overview

The problem asks you to reverse the given array of characters in-place. This means you cannot use extra memory for another array; instead, you must modify the input array directly.

Formally:
Given a character array s, reverse the order of the characters in it so that the first element becomes the last, and the last becomes the first.

You must do this using O(1) extra memory.

Example 1:

Input: s = ['h', 'e', 'l', 'l', 'o']
Output: ['o', 'l', 'l', 'e', 'h']

Example 2:

Input: s = ['H', 'a', 'n', 'n', 'a', 'h']
Output: ['h', 'a', 'n', 'n', 'a', 'H']

---

Intuition / Approach

The simplest and most efficient way to reverse an array in-place is by using the two-pointer technique.

We can use two pointers:

• One pointer starts from the beginning of the array (left index 0)
• Another pointer starts from the end of the array (right index s.length – 1)

Then, we repeatedly swap the characters at left and right until the two pointers meet in the middle.

This ensures that every element on the left is swapped with its corresponding element on the right, effectively reversing the array without using extra space.

---

Algorithm Explanation

1. Initialize two pointers:
   • left = 0
   • right = s.length - 1
2. While left < right:
   • Swap s[left] and s[right]
   • Increment left by 1
   • Decrement right by 1
3. When the loop finishes, the array is reversed in place.

---

Java Code Implementation

public class ReverseString {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        // Swap characters until the two pointers meet
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            
            // Move both pointers toward the center
            left++;
            right--;
        }
    }

    // Example usage
    public static void main(String[] args) {
        ReverseString solution = new ReverseString();
        char[] s = {'h', 'e', 'l', 'l', 'o'};
        solution.reverseString(s);
        System.out.println(s);  // Output: "olleh"
    }
}

---

Complexity Analysis

Time Complexity:

• Each character is swapped at most once.
• Therefore, the time complexity is O(n), where n is the number of characters in the array.

Space Complexity:

• Since we only use a few variables (left, right, and temp), no additional space proportional to input size is used.
• Hence, the space complexity is O(1).

---

Alternative Approaches

1. Using Recursion:
   A recursive solution can also reverse the array by swapping the first and last elements and then recursively calling the function for the remaining middle part.
   However, recursion introduces function call overhead and uses O(n) space due to the call stack, so it is less optimal.
2. Using a Stack (not in-place):
   We could push all elements into a stack and then pop them out to reverse the order, but this uses extra space, violating the in-place requirement.