In-place Reversal with Two Pointers

The "In-Place" Constraint: O(1) Space

A common requirement in algorithm problems is to perform an operation "in-place," which means modifying the given data structure directly rather than creating a new one. This is a constraint on space complexity, typically requiring it to be O(1), or constant space.

In Python, it's easy to reverse a list with slicing: new_list = old_list[::-1]. However, this operation creates a new, reversed copy of the list, consuming O(N) extra space, where N is the number of elements. This violates the in-place requirement.

The problem requires us to alter the original memory block of the array. To do this efficiently, we'll use a classic method: the two-pointer approach.

The Two-Pointer Algorithm for Reversal

The intuition behind in-place reversal is symmetrical swapping. The first element needs to be swapped with the last, the second with the second-to-last, and so on, until we reach the middle of the array.

We can manage this process cleanly with two pointers (which, in Python, are just integer indices):

1. Initialize a left pointer at the start of the array (index 0).
2. Initialize a right pointer at the end of the array (index len(s) - 1).
3. In a loop, as long as left is less than right:
   a. Swap the elements at the left and right indices.
   b. Move the left pointer one step to the right (left += 1).
   c. Move the right pointer one step to the left (right -= 1).

The loop terminates when the pointers meet or cross, at which point the array is fully reversed.

This diagram illustrates the process for both even and odd-length arrays. Notice how for an odd-length array, the middle element naturally stays in its correct place without needing to be swapped.

To solidify this logic, please read through a detailed explanation of the approach.

Python Implementation

With your background, the implementation should be straightforward. Python's tuple assignment syntax makes the swap operation particularly clean, avoiding the need for an explicit temporary variable.

Here is a typical implementation for LeetCode 344, which expects the List[str] to be modified in-place.

from typing import List

def reverseString(s: List[str]) -> None:
    """
    Reverses a list of characters in-place using the two-pointer technique.
    Does not return anything, modifies s directly.
    """
    left = 0
    right = len(s) - 1

    while left < right:



        # Pythonic swap using tuple unpacking
        s[left], s[right] = s[right], s[left]
        



        # Move pointers towards the center
        left += 1
        right -= 1




# Example usage:
my_string = ['h', 'e', 'l', 'l', 'o']
reverseString(my_string)
print(my_string)  # Output: ['o', 'l', 'l', 'e', 'h']

another_string = ['H', 'a', 'n', 'n', 'a', 'h']
reverseString(another_string)
print(another_string) # Output: ['h', 'a', 'n', 'n', 'a', 'H']

Loop Condition: while left < right

It's important to use < and not <=. If the list has an odd number of elements, the pointers will eventually meet at the middle element (left == right). A swap at this point (s[left], s[left] = s[left], s[left]) is redundant. Using < correctly stops the loop as soon as the pointers meet or cross.

Complexity Analysis

Understanding the performance of this algorithm is crucial for interviews.

• Time Complexity: O(N)
  The algorithm makes approximately N/2 swaps. Since we analyze complexity in terms of the input size N, this linear relationship results in a time complexity of O(N). Each element is touched and swapped at most once.

• Space Complexity: O(1)
  This is the key advantage of the in-place approach. We only use two integer variables (left and right) to store the indices. The amount of memory used does not grow with the size of the input array, so the space complexity is constant, or O(1).

The following video provides a concise walkthrough of the code and reinforces the complexity analysis.

Conclusion

In this lesson, we've refreshed a fundamental algorithm for in-place array reversal. You should now be comfortable implementing this pattern and explaining its efficiency.

Here are the key takeaways:

• In-place modification means altering the original data structure with O(1) extra space.
• Python's s[::-1] creates a new object and is not an in-place solution.
• The two-pointer technique is the standard, efficient method for in-place reversal. It works by swapping elements from both ends of the array and moving the pointers toward the center.
• The algorithm has a time complexity of O(N) and a space complexity of O(1).

This pattern is a building block. In the next lesson, we will extend this concept to solve a slightly more complex problem: reversing specific or alternating segments of an array, which requires applying the same two-pointer logic to sub-arrays.