Problem Description

You need to reverse a string that is given as an array of characters. The task requires you to modify the original array directly without creating a new array or using additional data structures.

Key Requirements:

• The input is an array of characters s representing a string
• You must modify the array in-place (directly change the original array)
• You can only use O(1) extra memory, meaning you cannot create another array or use space proportional to the input size
• The function should not return anything; it should only modify the input array

Example: If the input array is ['h', 'e', 'l', 'l', 'o'], after calling the function, the array should become ['o', 'l', 'l', 'e', 'h'].

The solution uses a two-pointer technique where one pointer i starts at the beginning of the array (index 0) and another pointer j starts at the end (index len(s) - 1). The algorithm repeatedly swaps the characters at positions i and j, then moves i forward and j backward. This process continues until the pointers meet in the middle, at which point the entire string has been reversed.

The swapping is done using Python's tuple assignment: s[i], s[j] = s[j], s[i], which exchanges the values at the two positions without needing a temporary variable. This approach ensures the space complexity remains O(1) as required.

Intuition

To reverse a string in-place, think about what "reversing" actually means - the first character should become the last, the second character should become the second-to-last, and so on. This naturally suggests a swapping pattern.

Consider a simple example: ['a', 'b', 'c', 'd']. To reverse it:

• 'a' (at position 0) should swap with 'd' (at position 3)
• 'b' (at position 1) should swap with 'c' (at position 2)

Notice that we're pairing elements from opposite ends and working our way toward the center. This observation leads us to the two-pointer approach:

• Start with one pointer at the beginning and another at the end
• Swap the elements they point to
• Move both pointers toward the center
• Stop when they meet or cross

Why does this work with O(1) space? Because we're only using two integer variables (i and j) to track positions, regardless of the array size. We're rearranging elements within the existing array rather than creating a new one.

The beauty of this approach is its symmetry - we process the array from both ends simultaneously, completing the reversal in exactly n/2 swaps where n is the array length. For odd-length arrays, the middle element naturally stays in place, which is exactly what we want.

Solution Approach

The implementation uses the two-pointer technique to reverse the string in-place:

1. Initialize two pointers: Set i = 0 to point to the first character and j = len(s) - 1 to point to the last character.

2. Swap and move pointers: While i < j:

   • Swap the characters at positions i and j using Python's tuple assignment: s[i], s[j] = s[j], s[i]
   • Move i forward by incrementing it: i = i + 1
   • Move j backward by decrementing it: j = j - 1

3. Termination condition: The loop continues as long as i < j. When i >= j, the pointers have either met (for even-length arrays) or crossed (for odd-length arrays), meaning all necessary swaps are complete.

Step-by-step example with s = ['h', 'e', 'l', 'l', 'o']:

• Initial: i = 0, j = 4, array = ['h', 'e', 'l', 'l', 'o']
• Iteration 1: Swap s[0] and s[4] → ['o', 'e', 'l', 'l', 'h'], then i = 1, j = 3
• Iteration 2: Swap s[1] and s[3] → ['o', 'l', 'l', 'e', 'h'], then i = 2, j = 2
• Stop: i is not less than j, so we exit the loop

The algorithm performs exactly ⌊n/2⌋ swaps where n is the array length, achieving O(n) time complexity with O(1) space complexity since we only use two extra variables regardless of input size.

Example Walkthrough

Let's walk through the solution with a small example: s = ['c', 'a', 't']

Initial Setup:

• Array: ['c', 'a', 't']
• i = 0 (pointing to 'c')
• j = 2 (pointing to 't')

Step 1: First swap

• Check condition: i < j? Yes (0 < 2), so continue
• Swap s[0] with s[2]: ['c', 'a', 't'] becomes ['t', 'a', 'c']
• Update pointers: i = 1, j = 1

Step 2: Check termination

• Check condition: i < j? No (1 is not less than 1)
• Exit the loop

Final Result: ['t', 'a', 'c']

The string "cat" has been successfully reversed to "tac" using only 1 swap operation. Notice how the middle character 'a' stayed in its position, which is correct for odd-length arrays. The algorithm used only two integer variables (i and j) for the entire process, maintaining O(1) space complexity.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm uses a two-pointer approach that traverses from both ends of the array toward the center. Each element is visited exactly once - the loop runs for n/2 iterations, and in each iteration, we perform a constant-time swap operation. Therefore, the total time complexity is O(n/2) which simplifies to O(n).

The space complexity is O(1). The algorithm only uses two integer variables i and j as pointers to track positions in the array, regardless of the input size. The swapping operation is done in-place without requiring any additional data structures that scale with the input size. The space used remains constant throughout the execution.

Common Pitfalls

1. Attempting to return the modified array

A frequent mistake is adding a return statement at the end of the function, which violates the problem requirements. The function signature specifies -> None, meaning it should modify the array in-place without returning anything.

Incorrect approach:

def reverseString(self, s: List[str]) -> None:
    left = 0
    right = len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    return s  # ❌ Wrong - should not return anything

Solution: Simply omit the return statement and let the function end naturally.

2. Using wrong loop condition (<= instead of <)

Using while left <= right instead of while left < right causes unnecessary operations. When the pointers meet at the same index, swapping an element with itself is redundant.

Incorrect approach:

while left <= right:  # ❌ Unnecessary swap when left == right
    s[left], s[right] = s[right], s[left]
    left += 1
    right -= 1

Solution: Use while left < right to stop when pointers meet or cross, avoiding pointless swaps.

3. Creating a new array instead of modifying in-place

Some might instinctively create a reversed copy and then try to assign it back, which violates the O(1) space requirement.

Incorrect approach:

def reverseString(self, s: List[str]) -> None:
    reversed_s = s[::-1]  # ❌ Creates O(n) extra space
    for i in range(len(s)):
        s[i] = reversed_s[i]

Solution: Stick to the two-pointer approach that swaps elements directly within the original array.

4. Forgetting to handle empty arrays or single characters

While the two-pointer approach naturally handles these edge cases (the while loop simply doesn't execute), explicitly checking for them can cause unnecessary code complexity or errors.

Overcomplicated approach:

def reverseString(self, s: List[str]) -> None:
    if len(s) <= 1:  # Unnecessary check
        return
    left = 0
    right = len(s) - 1
    # ... rest of the code

Solution: The standard two-pointer implementation already handles empty arrays and single characters correctly without special cases. For an empty array or single character, left < right is false from the start, so no swaps occur.