Reverse String Leetcode problem

Problem Statement:

Given a character array s, reverse the array in-place with O(1) extra memory.

Key Constraints:

• Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
• The input array s consists of printable ASCII characters.

Examples:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Explanation: The string "hello" is reversed to "olleh".

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] Explanation: The string "Hannah" is reversed to "hannaH".

Approach 1: Two-Pointer Iteration (The Beginner’s Way)

This approach uses two pointers, one starting from the beginning and the other from the end of the array, swapping elements until they meet in the middle.

Algorithm

• Initialize a left pointer at index 0 and a right pointer at the last index of the array.
• While left is less than right:
• Swap the characters at s[left] and s[right].
• Increment left by 1.
• Decrement right by 1.

Implementation

def reverseString(s):
    """
    Reverses a string (character array) in-place using two pointers.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]  # Swap characters
        left += 1
        right -= 1
    return s

Complexity Analysis

Time Complexity: O(n) — We iterate through approximately half of the array elements, performing a constant number of operations for each swap. Therefore, the time complexity is linear with respect to the number of elements n in the array.

Get ANAND VASHISHTHA’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Space Complexity: O(1) — We only use a few variables (left, right, and a temporary variable for swapping), which consume a constant amount of extra space regardless of the input size.

When to Use

• When memory usage is a critical concern.
• When the input array can be modified directly.
• For simple string or array reversal tasks.

Pros: Efficient in terms of space, easy to understand and implement. Cons: Modifies the input array in-place, which might not always be desired.

Approach 2: Recursion (The Elegant Way)

This approach uses recursion to swap characters from the ends towards the center of the array.

Algorithm

• Define a recursive helper function that takes the character array, a left index, and a right index as arguments.
• Base Case: If left is greater than or equal to right, stop the recursion.
• Recursive Step: Swap s[left] and s[right]. Then, recursively call the function with left + 1 and right - 1.

Implementation

def reverseStringRecursive(s):
    """
    Reverses a string (character array) in-place using recursion.
    Time: O(n), Space: O(n) (due to recursion stack)
    """
    def helper(left, right):
        if left < right:
            s[left], s[right] = s[right], s[left]
            helper(left + 1, right - 1)
    helper(0, len(s) - 1)
    return s

Complexity Analysis

Time Complexity: O(n) — Each recursive call performs a constant amount of work (swapping), and there are n/2 such calls. Thus, the time complexity is linear.

Space Complexity: O(n) — The recursion stack can go as deep as n/2 calls in the worst case (for an array of size n), leading to linear space complexity.

Execution Trace

Input: s = ["h","e","l","l","o"]
helper(0, 4):
  s = ["o","e","l","l","h"]
  helper(1, 3):
    s = ["o","l","l","e","h"]
    helper(2, 2):
      left (2) is not less than right (2). Base case met. Return.
  Return.
Return.
Final s = ["o","l","l","e","h"]

When to Use

• When a recursive solution is preferred for its elegance or to match a specific problem pattern.
• When the input size is small enough to not cause stack overflow issues.

Pros: Elegant and concise code for some, demonstrates understanding of recursion. Cons: Higher space complexity due to recursion stack, potential for stack overflow on very large inputs.

Approach 3: Pythonic Slice (The Pythonista’s Way)

While the problem statement specifies in-place modification with O(1) extra memory, a common Pythonic way to reverse a list is using slicing. This is not strictly O(1) space as it creates a new reversed list, but it’s worth mentioning for its simplicity in Python.

Algorithm

• Reassign the slice of the original list with the reversed slice of itself.

Implementation

def reverseStringPythonic(s):
    """
    Reverses a string (character array) using Python slicing (not in-place O(1) space).
    Time: O(n), Space: O(n)
    """
    s[:] = s[::-1]
    return s

Why This Works

The s[:] = s[::-1] syntax works because s[::-1] creates a reversed copy of the list s. The s[:] = ... then assigns the elements of this new reversed list back into the original list s, effectively modifying s in-place. However, the temporary reversed copy s[::-1] requires O(n) space, which violates the O(1) extra memory constraint for the problem, but is a very common and efficient way to reverse lists in Python when the space constraint is not strict.