Reverse String

▶

Steps

setup

Initialize pointers

The helper function is called with left pointer at index 0 and right pointer at index 4, the ends of the array.

💡 Setting pointers at opposite ends is the foundation of the two-pointer approach for reversing.

Line:

helper(0, len(s) - 1)

💡 The algorithm will swap characters at these pointers and then move inward.

compare

Check base case: left < right

Check if left pointer (0) is greater than or equal to right pointer (4). Since 0 < 4, continue swapping.

💡 This condition stops recursion when pointers meet or cross, meaning reversal is complete.

Line:

if left >= right:
    return

💡 The recursion continues because there are still characters to swap.

swap

Swap characters at left and right

Swap characters at indices 0 and 4: 'h' and 'o' are exchanged.

💡 Swapping moves the character from the start to the end and vice versa, reversing the string step-by-step.

Line:

s[left], s[right] = s[right], s[left]

💡 Swapping is the core operation that reverses the string in place.

traverse

Recursive call with pointers moved inward

Call helper recursively with left incremented to 1 and right decremented to 3 to continue swapping inner characters.

💡 Moving pointers inward narrows the range to reverse the middle part of the string.

Line:

helper(left + 1, right - 1)

💡 The recursion moves closer to the base case by shrinking the problem size.

compare

Check base case: left < right

Check if left pointer (1) is greater than or equal to right pointer (3). Since 1 < 3, continue swapping.

💡 The base case check ensures recursion stops when pointers meet or cross.

Line:

if left >= right:
    return

💡 The algorithm continues because there are still characters to swap.

swap

Swap characters at left and right

Swap characters at indices 1 and 3: 'e' and 'l' are exchanged.

💡 Swapping inner characters continues reversing the string from the outside in.

Line:

s[left], s[right] = s[right], s[left]

💡 Each swap moves the string closer to fully reversed.

traverse

Recursive call with pointers moved inward

Call helper recursively with left incremented to 2 and right decremented to 2 to check the middle character.

💡 Pointers move inward to the middle character, which does not need swapping.

Line:

helper(left + 1, right - 1)

💡 The recursion approaches the base case where pointers meet.

compare

Check base case: left >= right

Check if left pointer (2) is greater than or equal to right pointer (2). Since 2 == 2, base case reached, stop recursion.

💡 When pointers meet or cross, the string is fully reversed.

Line:

if left >= right:
    return

💡 No more swaps needed; reversal is complete.

prune

Return from recursion

The recursion unwinds as base case is met; no further operations are performed.

💡 Returning from recursion means all swaps are done and the string is reversed.

Line:

return

💡 The algorithm completes after all recursive calls return.

reconstruct

Final reversed string

The final reversed string is ['o','l','l','e','h'], ready to be returned or printed.

💡 The array now holds the reversed string after all swaps.

Line:

print(s)

💡 The two-pointer recursive approach successfully reversed the string in place.

def reverseString(s):
    def helper(left, right):
        # STEP 2: Check base case
        if left >= right:
            return
        # STEP 3: Swap characters
        s[left], s[right] = s[right], s[left]
        # STEP 4: Recursive call with pointers moved inward
        helper(left + 1, right - 1)

# Driver code
if __name__ == "__main__":
    s = ['h','e','l','l','o']
    # STEP 1: Initialize pointers
    helper = lambda left, right: None  # placeholder
    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)  # STEP 1 call
    # STEP 10: Print final reversed string
    print(s)

📊

Reverse String - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement helps you understand how the two-pointer technique efficiently reverses the string without extra space.

compare

left

h

0

e

1

l

2

l

3

right

o

4

compare

left

h

0

e

1

l

2

l

3

right

o

4

swap

left

o

0

e

1

l

2

l

3

right

h

4

move_left

o

0

left

e

1

l

2

right

l

3

h

4

compare

o

0

left

e

1

l

2

right

l

3

h

4

swap

o

0

left

l

1

l

2

right

e

3

h

4

move_left

o

0

l

1

right

l

2

e

3

h

4

compare

o

0

l

1

right

l

2

e

3

h

4

prune

o

0

l

1

l

2

e

3

h

4

record

o

0

l

1

l

2

e

3

h

4

Result: ["o","l","l","e","h"]

Key Takeaways

✓ Two pointers starting at opposite ends swap characters moving inward to reverse the string efficiently.

This insight is hard to see from code alone because the pointer movements and swaps happen recursively and implicitly.

✓ The base case stops recursion when pointers meet or cross, ensuring no unnecessary swaps.

Visualizing the base case clarifies why the recursion terminates exactly when the string is fully reversed.

✓ Each recursive call reduces the problem size by moving pointers inward, showing divide-and-conquer in action.

Seeing the pointers move inward step-by-step helps understand how recursion narrows the problem.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given a sorted array and need to remove duplicates such that each element appears at most twice, modifying the array in-place. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Using a nested loop to count duplicates and shift elements accordingly

B. Using two pointers where the write pointer only advances if the current element differs from the element two positions before

C. Using a hash map to count occurrences and then reconstruct the array

D. Using dynamic programming to track the maximum allowed duplicates

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, and duplicates are allowed at most twice, so we can leverage order.

2. Step 2: Identify the approach that uses two pointers and index offset check

   This approach compares the current element with the element two positions before the write pointer to decide if it should be written, ensuring O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers with index offset check is the known optimal approach [OK]

Hint: Two pointers with offset check is optimal [OK]

Common Mistakes:

• Using nested loops causes O(n²) time
• Hash maps use extra space
• DP is unnecessary here

3. You are given a string and need to determine if it reads the same forwards and backwards, ignoring case and non-alphanumeric characters. Which approach guarantees an optimal O(n) time and O(n) space solution for this problem?

easy

A. Reverse the original string and compare it directly to the input string without any preprocessing.

B. Use dynamic programming to check all substrings for palindrome properties.

C. Use a greedy approach to skip characters that don't match and try to fix mismatches on the fly.

D. Preprocess the string by removing non-alphanumeric characters and converting to lowercase, then use two pointers from opposite ends to compare characters.

Solution

1. Step 1: Understand problem constraints

   The problem requires ignoring case and non-alphanumeric characters, so direct comparison or naive reversal won't work correctly.

2. Step 2: Identify approach that handles preprocessing and efficient comparison

   Preprocessing to clean the string and then using two pointers from opposite ends ensures O(n) time and space, and correctly handles all cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Preprocessing + two pointers is standard for palindrome checks ignoring punctuation [OK]

Hint: Preprocess then two pointers is optimal palindrome check [OK]

Common Mistakes:

• Trying to compare original string directly without cleaning
• Using DP which is overkill and slower
• Greedy skipping mismatches leads to incorrect results

4. Suppose the array is not sorted and you want to remove duplicates in-place with O(1) extra space. Which modification to the two-pointer approach is correct?

hard

A. Scan the array multiple times with nested loops to remove duplicates.

B. Use two pointers without sorting, comparing elements directly to remove duplicates.

C. Use a hash set to track duplicates and overwrite duplicates in-place.

D. Sort the array first, then apply the two-pointer approach.

Solution

1. Step 1: Understand constraints

   Two-pointer approach relies on sorted array to detect duplicates in one pass.

2. Step 2: Identify correct modification

   Sorting first ensures duplicates are adjacent, enabling two-pointer removal in O(n log n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting enables two-pointer approach on unsorted input [OK]

Hint: Two-pointer requires sorted array; sort first if unsorted [OK]

Common Mistakes:

• Trying two-pointer without sorting
• Using extra space violating constraints

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