Katkat
Back

Reverse a Character Array In Place

CargurusData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to manipulate array elements in-place using two-pointer logic while adhering to strict space complexity constraints.

Problem Statement

Given an array of characters s, write a function that reverses the string in-place. You must modify the input array directly with O(1) extra memory. Do not use built-in language methods like reverse() or create a new array or list.

Function Signature

def reverse_string(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """

Examples

Example 1: Input: s = ["h","e","l","l","o"] Output: s = ["o","l","l","e","h"]

Example 2: Input: s = ["C","a","r","G","u","r","u","s"] Output: s = ["s","u","r","u","G","r","a","C"]

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is a printable ASCII character.
  • You must solve this with O(1) extra space.

Edge Cases

  • Empty array (though constrained by length 1).
  • Single character array (no change required).
  • Arrays with even vs. odd numbers of elements.

Hints

Hint 1

Think about using two pointers: one starting at the beginning of the array and one at the end.

Hint 2

Swap the characters at the two pointers and move them toward the center until they meet or cross.

Hint 3

Ensure your loop termination condition correctly handles both odd and even array lengths.

Follow-up questions

  • How would your approach change if you were asked to reverse the words in the string instead of the individual characters?
  • What are the implications of the O(1) space complexity requirement if the input was a large string instead of a mutable array?
  • Can you implement this using recursion instead of an iterative loop, and what would the stack space complexity be in that case?