Reversing Array/String Segments

Introduction

In our previous lesson, we established the fundamental two-pointer technique for reversing an entire array or string in-place. We saw how this O(1) space approach is a highly efficient solution for problems like LeetCode's "Reverse String."

Today, we will build directly on that foundation. The goal is to apply the same reversal logic not to the whole array, but to specific segments within it. This is a versatile pattern that unlocks solutions to a variety of problems, including reversing parts of a string in a specific rhythm or even rotating an entire array with constant extra space. Mastering this will add a powerful, reusable tool to your algorithmic problem-solving kit.

Generalizing the Two-Pointer Reversal

The first step is to recognize that the two-pointer reversal logic from last time is not limited to the full array. It can operate on any continuous segment. We can encapsulate this logic into a reusable helper function.

Given an array arr, a left index, and a right index, we can reverse the sub-array arr[left...right] using the exact same swapping mechanism.

def reverse_segment(arr: list, left: int, right: int) -> None:
    """Reverses a segment of an array in-place from left to right indices."""
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# Example: Reverse the middle part of an array
data = [10, 20, 30, 40, 50, 60]
# Reverse the segment from index 2 to 4 (i.e., [30, 40, 50])
reverse_segment(data, 2, 4)
print(data) # Output: [10, 20, 50, 40, 30, 60]

With this utility, we can now tackle more complex problems by simply identifying the correct left and right boundaries for each reversal.

Pattern 1: Reversing in Fixed-Size Groups

A common problem variation asks you to reverse an array in adjacent groups of a given size, k. For example, if k=3 and the array is [1, 2, 3, 4, 5, 6, 7, 8], the result should be [3, 2, 1, 6, 5, 4, 8, 7].

The strategy is to iterate through the array with a step of k. In each step, we are at the beginning of a new group. We then apply our reverse_segment logic to that group. A key detail is handling the final group, which may be smaller than k.

The two-pointer pattern can be adapted for various scenarios. For reversing segments, we apply the converging pointers (right image) to subsections of an array.

The following resource provides a clear explanation and a concise implementation of this pattern.

Reverse an Array in groups - GeeksforGeeks

This GeeksforGeeks article breaks down the problem of reversing an array in fixed-size groups. It's a direct application of what we're discussing.

First, read the problem description and examples to understand the requirements fully. Then, review the high-level approach. Finally, examine the Python code provided. In the reverseInGroups function, notice how the right boundary is calculated using min(i + k - 1, n - 1) to gracefully handle the last, potentially smaller, group.

The core logic from the article can be expressed using our helper function like this:

def reverseInGroups(arr, n, k):
    for i in range(0, n, k):
        left = i
        # Find the end of the current group, handling the boundary
        right = min(i + k - 1, n - 1)
        # Reverse this specific segment
        reverse_segment(arr, left, right)

This clean, modular approach is exactly what you should aim for in an interview setting.

Pattern 2: Reversing Alternating Segments (LeetCode 541)

Let's look at a slightly different problem: given a string s and an integer k, you must reverse the first k characters for every 2k characters, starting from the beginning. This is LeetCode problem 541, "Reverse String II."

The key insight is to iterate through the string in chunks of 2k. For each chunk, you only apply the reversal to the first k characters.

541. Reverse String II - In-Depth Explanation

This AlgoMonster article provides an excellent, detailed walkthrough of this specific problem. It highlights a very Pythonic way to solve it.

Read the problem description and the Intuition section to grasp the 2k stepping pattern. Then, follow the Solution Approach and analyze the provided Python code. Pay close attention to two points: Strings are immutable in Python, so the solution first converts the string to a list of characters. The line char_list[start_index : start_index + k] = reversed(...) is a powerful Python idiom. It performs an in-place modification of the list slice using an iterator, which is both readable and efficient.

While the AlgoMonster solution uses a Pythonic slice assignment, you could also solve it using the reverse_segment helper function we defined earlier. The logic remains the same: iterate with a step of 2k and apply reversal to the segment from i to min(i + k - 1, n - 1).

Pattern 3: Array Rotation via Reversals (LeetCode 189)

Perhaps the most elegant application of segment reversal is the three-reversal algorithm for rotating an array. The problem is to rotate an array to the right by k steps. A naive solution might use O(k*N) time or O(N) space, but we can do it in O(N) time and O(1) space with our new tool.

The algorithm is as follows:

Reverse the entire array.
Reverse the first k elements.
Reverse the remaining n-k elements.

This sequence of operations magically results in the correctly rotated array. For instance, to rotate [1, 2, 3, 4, 5] by k=2:

Reverse all: [5, 4, 3, 2, 1]
Reverse first k=2: [4, 5, 3, 2, 1]
Reverse rest (n-k=3): [4, 5, 1, 2, 3]
The final array is [4, 5, 1, 2, 3], which is the original array rotated right by 2.

This video from NeetCode provides an excellent visual explanation of this non-obvious trick.

Rotate Array - Leetcode 189 - Python

This video covers multiple solutions for LeetCode 189, "Rotate Array". We are interested in the clever O(1) space solution.

Watch the section that introduces the three-reversal technique. The visual breakdown makes it clear how this counter-intuitive process works. Afterward, you can review the code implementation, which shows how to apply this logic by defining the correct boundaries for each of the three reversal calls.

Conclusion

Today we've seen how a single, simple algorithm—in-place segment reversal—can be a powerful building block for solving a range of more complex problems.

Key takeaways from this lesson include:

Generalization is Key: Encapsulating the two-pointer reversal logic into a reverse(arr, left, right) function makes your code cleaner and more reusable.
Identify the Pattern: Many problems involving array or string manipulation can be broken down into a series of segment reversals. The main task is to correctly identify the start and end indices for each reversal.
Three Common Applications:
1. Fixed Groups: Iterate with a step of k and reverse each group.
2. Alternating Segments: Iterate with a step of 2k and reverse the first k elements of each block.
3. Array Rotation: Use the three-reversal algorithm (reverse all, reverse first k, reverse rest) for an elegant O(1) space solution.

In our next lesson, we'll extend the two-pointer pattern again. We will explore how to selectively reverse elements that match a certain condition (e.g., only reversing letters in a string with numbers), while leaving other elements in their original positions.