Reverse String

Difficulty: Easy

Problem

Write a function that flips a string end to end. The string arrives as an array of characters s, and you must rearrange that same array in place using only O(1) extra memory (no second array). Solve it using recursion.

Example

Input: s = ["w","o","r","l","d"]
Output: ["d","l","r","o","w"]
Explanation: The characters are swapped in place from the outside in: 'w' with 'd', then 'o' with 'l', leaving 'r' in the middle.

Brute-force approach

The plain way is to build a new reversed list: read the tiles from the last to the first and write them into a second list. That is n reads, n writes and n extra tiles of memory, which this problem forbids (it asks for an in-place answer with O(1) extra memory).

Steps

  1. Make an empty list called out
  2. Read s from the last tile to the first, appending each tile to out
  3. Return out (the problem forbids this: it needs n extra tiles)

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses n extra tiles of memory, but the problem asks for O(1) extra memory
  • Does not change s in place

Optimal approach

Key insight: If someone magically reverses the inner portion of the array for you, all you need to do is swap the outermost pair. That's it!

Use the Leap of Faith recipe: swap the outermost pair, then trust recursion to reverse the inner portion. Two pointers (left, right) move inward with each call.

Steps

  1. Call helper(s, 0, s.length - 1)
  2. Base case: if left >= right, return
  3. Swap s[left] and s[right]
  4. Leap of Faith: helper(s, left + 1, right - 1)

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function reverseString(s):
    helper(s, 0, len(s) - 1)

function helper(s, left, right):
    if left >= right:
        return
    swap s[left] and s[right]
    helper(s, left + 1, right - 1)

Hints

  • What is the simplest array that's already reversed? (Base case: 0 or 1 element)
  • If someone magically reverses the inner portion, what's left to do? (Swap the outermost pair!)
  • Two pointers: left and right move inward with each recursive call
  • The two end tiles are final once swapped. Whatever is inside, the answer's inside is its reverse, so one call on the inner part finishes the job.

Complexity questions

What is the time complexity of the recursive reversal?

O(n). We make floor(n/2) swaps, one per call, plus one last call that stops (floor(n/2) + 1 calls in total), each doing O(1) work. Total: about n/2 = O(n).

What is the space complexity (call stack)?

O(n). The pile is at most floor(n/2) + 1 calls deep. Each frame uses constant space. Total stack space: about n/2 = O(n). The recursive call is the last statement (a tail call): some languages remove the pile for tail calls, but Python and Java do not, so the space stays O(n). Python also stops at 1,000 waiting calls by default, so this solution fails for lists longer than about 2,000 characters (about 1,995 from the top of a script): for large inputs the O(1)-space loop is the safe answer.

How many swaps does reversing a 6-element array require?

3. floor(6/2) = 3 swaps: (index 0↔5), (index 1↔4), (index 2↔3). Each recursive call handles one pair.

Check your understanding of Reverse String

If someone magically reverses the inner portion [e, l, l] of [h, e, l, l, o] to get [h, l, l, e, o], what do you still need to do?

Swap h and o (the outermost pair). That's the Leap of Faith! Trust the recursion to handle the inner portion. You just swap the outermost pair (h ↔ o). Together: [o, l, l, e, h]. Done!

What is the base case for recursive reversal?

When left >= right (0 or 1 elements left). When left >= right, there are 0 or 1 elements in the subproblem, already 'reversed' by definition. No swap needed!

How many swaps does reversing a 5-element array require?

2. We swap pairs from outside in: (index 0 ↔ 4) and (index 1 ↔ 3). The middle element stays. That's floor(n/2) = 2 swaps.

Related problems

Keep practising