Reverse String easy

Problem Statement

Given an array of characters s, reverse the order of characters in-place. You must do this without allocating extra space for another array. You may assume all the characters consist of printable ascii characters.

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"]

Steps to Solve

1. Two Pointers: We'll use two pointers, left and right, initially pointing to the beginning and end of the array respectively.

2. Swap: Swap the characters at the left and right pointers.

3. Move Pointers: Increment the left pointer and decrement the right pointer.

4. Repeat: Continue steps 2 and 3 until the left pointer is greater than or equal to the right pointer. This signifies that we've reached the middle of the array, and all swaps have been performed.

Explanation

The algorithm uses the concept of two pointers to efficiently reverse the array in-place. By swapping characters from the beginning and end simultaneously, we avoid the need for extra space. The loop continues until the pointers cross, guaranteeing that the entire array is reversed.

Code (C#)

public class Solution {
    public void ReverseString(char[] s) {
        int left = 0;
        int right = s.Length - 1;

        while (left < right) {
            // Swap characters
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            // Move pointers
            left++;
            right--;
        }
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through approximately half the array (n/2) to perform the swaps.
• Space Complexity: O(1). We are using only a constant amount of extra space for the left, right, and temp variables. The reversal is done in-place, meaning we don't create a new array.