Reverse String

🎯

Reverse String

easyTWO_POINTERAmazonGoogle

Imagine you have a secret message written backwards, and you want to read it correctly by reversing the letters in place.

💡 This problem is a classic example of using two pointers to manipulate arrays or strings in place. Beginners often struggle because they try to create new strings instead of swapping characters directly, which is less efficient.

📋

Problem Statement

Given an array of characters s, reverse the array in place. You must do this by modifying the input array directly with O(1) extra memory.

1 ≤ n ≤ 10^5s[i] is a printable ASCII character

💡

Example

Input"['h','e','l','l','o']"

Output['o','l','l','e','h']

Swapping characters from opposite ends until the middle reverses the string.

• Single character array → same array
• Array with all identical characters → same array
• Empty array → no change
• Array with two characters → swapped

⚠️

Common Mistakes

Using extra space unnecessarily

Consumes more memory than needed, interviewers may see this as inefficient

✅ Use two-pointer swapping to reverse in place

Off-by-one errors in pointer initialization or loop condition

May cause index out of range errors or incomplete reversal

✅ Initialize pointers at 0 and n-1, loop while left < right

Not swapping characters correctly (e.g., forgetting temp variable in Java)

Characters get overwritten incorrectly, resulting in wrong output

✅ Use a temporary variable or tuple unpacking to swap safely

Using recursion without considering stack overflow

Program crashes on large inputs due to deep recursion

✅ Prefer iterative two-pointer approach for large inputs

🧠

Brute Force (Using Extra Space)

💡 This approach exists to build intuition by solving the problem straightforwardly without worrying about space efficiency. It helps beginners understand the reversal concept before optimizing.

Intuition

Create a new array and copy characters from the original array in reverse order, then copy back to the original array.

Algorithm

1. Create a new array of the same length as the input.
2. Copy characters from the input array to the new array in reverse order.
3. Copy the reversed characters back to the original array.
4. Return or finish as the input array is modified in place.

💡 This algorithm is easy to understand but uses extra space, which is not optimal but helps grasp the reversal process.

</>

Code

def reverseString(s):
    n = len(s)
    rev = [''] * n
    for i in range(n):
        rev[i] = s[n - 1 - i]
    for i in range(n):
        s[i] = rev[i]

# Driver code
if __name__ == "__main__":
    s = ['h','e','l','l','o']
    reverseString(s)
    print(s)

Line Notes

n = len(s)Determine the length of the input to know how many characters to process

rev = [''] * nInitialize a new list to store reversed characters

for i in range(n)Iterate over each index to copy characters in reverse order

s[i] = rev[i]Overwrite the original array with reversed characters to modify in place

import java.util.Arrays;
public class ReverseString {
    public static void reverseString(char[] s) {
        int n = s.length;
        char[] rev = new char[n];
        for (int i = 0; i < n; i++) {
            rev[i] = s[n - 1 - i];
        }
        for (int i = 0; i < n; i++) {
            s[i] = rev[i];
        }
    }
    public static void main(String[] args) {
        char[] s = {'h','e','l','l','o'};
        reverseString(s);
        System.out.println(Arrays.toString(s));
    }
}

Line Notes

int n = s.length;Get the length of the input array for iteration

char[] rev = new char[n];Create a new array to hold reversed characters

rev[i] = s[n - 1 - i];Copy characters from the end of original array to the start of new array

s[i] = rev[i];Copy reversed characters back to original array to modify in place

#include <iostream>
#include <vector>
using namespace std;

void reverseString(vector<char>& s) {
    int n = s.size();
    vector<char> rev(n);
    for (int i = 0; i < n; i++) {
        rev[i] = s[n - 1 - i];
    }
    for (int i = 0; i < n; i++) {
        s[i] = rev[i];
    }
}

int main() {
    vector<char> s = {'h','e','l','l','o'};
    reverseString(s);
    for (char c : s) cout << c;
    cout << endl;
    return 0;
}

Line Notes

int n = s.size();Get the size of the vector for iteration

vector<char> rev(n);Create a new vector to store reversed characters

rev[i] = s[n - 1 - i];Copy characters from the end of original vector to the start of new vector

s[i] = rev[i];Overwrite original vector with reversed characters

function reverseString(s) {
    const n = s.length;
    const rev = new Array(n);
    for (let i = 0; i < n; i++) {
        rev[i] = s[n - 1 - i];
    }
    for (let i = 0; i < n; i++) {
        s[i] = rev[i];
    }
}

// Test
const s = ['h','e','l','l','o'];
reverseString(s);
console.log(s);

Line Notes

const n = s.length;Store length of input array for iteration

const rev = new Array(n);Create a new array to hold reversed characters

rev[i] = s[n - 1 - i];Copy characters from the end of original array to the start of new array

s[i] = rev[i];Copy reversed characters back to original array to modify in place

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over the array twice, each O(n), and use extra O(n) space for the reversed array.

💡 For n=100000, this means about 200,000 operations and 100,000 extra spaces, which is inefficient for large inputs.

Interview Verdict: Accepted but not optimal

This approach works but uses extra space, which is not ideal for in-place reversal problems.

🧠

Two Pointers (In-Place Swap)

💡 This approach improves space efficiency by swapping characters in place using two pointers, a common technique in array/string problems.

Intuition

Use two pointers starting at opposite ends of the array and swap characters while moving towards the center.

Algorithm

1. Initialize two pointers: left at 0 and right at n-1.
2. While left < right, swap characters at left and right.
3. Increment left and decrement right to move towards the center.
4. Stop when pointers meet or cross.

💡 This algorithm is intuitive once you understand the two-pointer technique and avoids extra space.

</>

Code

def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# Driver code
if __name__ == "__main__":
    s = ['h','e','l','l','o']
    reverseString(s)
    print(s)

Line Notes

left, right = 0, len(s) - 1Initialize pointers at opposite ends to start swapping

while left < right:Continue swapping until pointers meet or cross

s[left], s[right] = s[right], s[left]Swap characters at the two pointers

left += 1Move left pointer inward after swap

import java.util.Arrays;
public class ReverseString {
    public static void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
    public static void main(String[] args) {
        char[] s = {'h','e','l','l','o'};
        reverseString(s);
        System.out.println(Arrays.toString(s));
    }
}

Line Notes

int left = 0, right = s.length - 1;Set pointers at the start and end of the array

while (left < right)Loop until pointers meet or cross

char temp = s[left];Store left character temporarily for swapping

left++;Move left pointer inward after swap

#include <iostream>
#include <vector>
using namespace std;

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

int main() {
    vector<char> s = {'h','e','l','l','o'};
    reverseString(s);
    for (char c : s) cout << c;
    cout << endl;
    return 0;
}

Line Notes

int left = 0, right = s.size() - 1;Initialize two pointers at opposite ends

while (left < right)Loop until pointers meet or cross

swap(s[left], s[right]);Swap characters at the two pointers

left++;Move left pointer inward after swap

function reverseString(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
}

// Test
const s = ['h','e','l','l','o'];
reverseString(s);
console.log(s);

Line Notes

let left = 0, right = s.length - 1;Initialize pointers at the start and end

while (left < right)Loop until pointers meet or cross

[s[left], s[right]] = [s[right], s[left]];Swap characters using destructuring assignment

left++;Move left pointer inward after swap

⏱

Complexity

TimeO(n)

SpaceO(1)

We swap characters in place with a single pass, so time is linear and space is constant.

💡 For n=100000, this means about 50,000 swaps, which is efficient and uses no extra memory.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews because it is both time and space efficient.

🧠

Recursive Two Pointers

💡 This approach uses recursion to swap characters from opposite ends, reinforcing understanding of recursion and two-pointer technique.

Intuition

Recursively swap the first and last characters, then recurse on the substring excluding those characters.

Algorithm

1. Define a helper function with left and right pointers.
2. If left >= right, return (base case).
3. Swap characters at left and right.
4. Recursively call helper with left+1 and right-1.

💡 This algorithm is elegant but uses call stack space, which may be a downside for large inputs.

</>

Code

def reverseString(s):
    def helper(left, right):
        if left >= right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)
    helper(0, len(s) - 1)

# Driver code
if __name__ == "__main__":
    s = ['h','e','l','l','o']
    reverseString(s)
    print(s)

Line Notes

def helper(left, right):Define recursive function with two pointers

if left >= right:Base case: pointers have met or crossed, stop recursion

s[left], s[right] = s[right], s[left]Swap characters at current pointers

helper(left + 1, right - 1)Recurse inward by moving pointers

import java.util.Arrays;
public class ReverseString {
    public static void reverseString(char[] s) {
        helper(s, 0, s.length - 1);
    }
    private static void helper(char[] s, int left, int right) {
        if (left >= right) return;
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        helper(s, left + 1, right - 1);
    }
    public static void main(String[] args) {
        char[] s = {'h','e','l','l','o'};
        reverseString(s);
        System.out.println(Arrays.toString(s));
    }
}

Line Notes

helper(s, 0, s.length - 1);Start recursion with pointers at array ends

if (left >= right) return;Base case to stop recursion when pointers meet or cross

char temp = s[left]; s[left] = s[right]; s[right] = temp;Swap characters at pointers

helper(s, left + 1, right - 1);Recursive call moving pointers inward

#include <iostream>
#include <vector>
using namespace std;

void helper(vector<char>& s, int left, int right) {
    if (left >= right) return;
    swap(s[left], s[right]);
    helper(s, left + 1, right - 1);
}

void reverseString(vector<char>& s) {
    helper(s, 0, s.size() - 1);
}

int main() {
    vector<char> s = {'h','e','l','l','o'};
    reverseString(s);
    for (char c : s) cout << c;
    cout << endl;
    return 0;
}

Line Notes

if (left >= right) return;Base case to stop recursion when pointers meet or cross

swap(s[left], s[right]);Swap characters at current pointers

helper(s, left + 1, right - 1);Recursive call moving pointers inward

helper(s, 0, s.size() - 1);Initial call to start recursion

function reverseString(s) {
    function helper(left, right) {
        if (left >= right) return;
        [s[left], s[right]] = [s[right], s[left]];
        helper(left + 1, right - 1);
    }
    helper(0, s.length - 1);
}

// Test
const s = ['h','e','l','l','o'];
reverseString(s);
console.log(s);

Line Notes

function helper(left, right) {Define recursive helper with two pointers

if (left >= right) return;Base case to stop recursion when pointers meet or cross

[s[left], s[right]] = [s[right], s[left]];Swap characters at pointers using destructuring

helper(left + 1, right - 1);Recursive call moving pointers inward

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Each recursive call processes one pair of characters, total n/2 calls, so linear time. Space is linear due to call stack.

💡 For n=100000, recursion depth is 50,000, which risks stack overflow in some languages.

Interview Verdict: Accepted but not recommended for large inputs

Recursion is elegant but can cause stack overflow; iterative two-pointer is safer.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the two-pointer in-place swap approach for optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extra Space)	O(n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers (In-Place Swap)	O(n)	O(1)	No	N/A	Code this approach
3. Recursive Two Pointers	O(n)	O(n) due to recursion stack	Yes	N/A	Mention as alternative, avoid coding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input/output and constraints.Step 2: Describe the brute force approach using extra space.Step 3: Optimize to two-pointer in-place swapping.Step 4: Optionally mention recursive approach if time permits.Step 5: Code the optimal approach and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of in-place algorithms, pointer manipulation, and ability to optimize space complexity.

Common Follow-ups

• What if the input is immutable? → Create a new reversed string.
• Can you reverse only a substring? → Adjust pointers to substring indices.

💡 These follow-ups test flexibility and understanding of string immutability and partial operations.

🔍

Pattern Recognition

When to Use

1) Need to reverse or reorder elements, 2) In-place modification required, 3) Two ends of array/string involved, 4) Constant extra space desired

Signature Phrases

reverse the array in placeswap characters from opposite ends

NOT This Pattern When

Problems requiring sorting or dynamic programming are different patterns.

Similar Problems

Reverse Words in a String - similar two-pointer reversalReverse Vowels of a String - two pointers with condition checks

Practice

1. Consider the following Python function that finds the minimum difference between k closest elements in an array. What is the returned value when arr = [4, 1, 7, 9] and k = 2?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 4, 7, 9].

2. Step 2: Slide window of size 2 and compute differences

   Windows: [1,4] diff=3, [4,7] diff=3, [7,9] diff=2. Minimum difference is 2.

3. Step 3: Re-examine calculations

   Check carefully: differences are 3, 3, and 2. Minimum is 2, so answer is 2.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Minimum difference between any two sorted elements is 2 [OK]

Hint: Sort array, check adjacent pairs for min difference [OK]

Common Mistakes:

• Off-by-one error in window boundaries
• Confusing difference calculation with max-min of unsorted subset
• Returning 0 prematurely without checking all windows

2. What is the time complexity of the optimal two-pointer forward approach for comparing two strings with backspaces, each of length n and m respectively?

medium

A. O(n * m)

B. O(n^2 + m^2)

C. O(n + m)

D. O(max(n, m) * log(max(n, m)))

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm processes each string once with a single pass using two pointers, so each character is visited at most once.

2. Step 2: Combine complexities for both strings

   Processing both strings independently takes O(n) and O(m), so total time is O(n + m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass per string, no nested loops [OK]

Hint: Two pointers scan each string once -> O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing space complexity with time
• Thinking backspace processing requires DP or sorting

3. What is the time complexity of the optimal two-pointer solution for the Container With Most Water problem, and why?

medium

A. O(n^2) because each pointer moves multiple times and all pairs are checked.

B. O(n) because each pointer moves inward at most n times, scanning the array once.

C. O(n log n) due to sorting or binary search steps involved.

D. O(1) because only constant space and operations are used.

Solution

1. Step 1: Analyze pointer movements

   Each pointer starts at opposite ends and moves inward only when the shorter line pointer moves, so total moves per pointer ≤ n.

2. Step 2: Count total operations

   Since pointers move inward without revisiting positions, total iterations ≤ n, making time complexity O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer linear scan -> O(n) time [OK]

Hint: Two pointers each move at most n times -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing space complexity with time
• Thinking sorting is required

4. Identify the bug in the following code snippet that attempts to implement the two-pointer approach for the Squares of a Sorted Array problem:

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = 0
    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] * nums[left]
            left += 1
        else:
            result[pos] = nums[right] * nums[right]
            right -= 1
        pos += 1
    return result

What is the bug?

medium

A. The comparison uses abs(nums[left]) > abs(nums[right]) instead of >=, causing off-by-one errors.

B. The output array is filled from the start (pos=0) instead of from the end, causing incorrect order.

C. The loop condition should be left < right, not left <= right, causing index errors.

D. The input array is modified in place, which is not allowed.

Solution

1. Step 1: Analyze how result array is filled

   The largest squares should be placed at the end of the result array, but pos starts at 0 and increments.

2. Step 2: Identify correct filling direction

   Filling from start causes the array to be sorted in descending order, not ascending.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output order incorrect due to filling direction [OK]

Hint: Fill output from end to maintain ascending order [OK]

Common Mistakes:

• Filling output array from start instead of end
• Incorrect loop boundary conditions
• Modifying input array without permission

5. If the problem changes so that elements equal to val can appear multiple times and must be removed, but the array is read-only and cannot be modified in-place, which approach is correct?

hard

A. Use the two pointers swap approach to modify the array in-place

B. Use the brute force nested loop shifting approach

C. Create a new array and copy only elements not equal to val, returning its length

D. Sort the array and then remove val elements by slicing

Solution

1. Step 1: Understand read-only constraint

   Cannot modify input array in-place, so approaches that swap or shift in-place are invalid.

2. Step 2: Choose correct approach

   Creating a new array copying only allowed elements respects read-only constraint and removes val elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   New array creation is necessary when input is immutable [OK]

Hint: Read-only input -> must copy to new array [OK]

Common Mistakes:

• Trying to modify read-only array in-place
• Using inefficient nested loops unnecessarily