Identifying reversal subproblem

Some problems may consist of smaller subproblems that can be solved using the reversal technique. Solving these subproblems may either partially or fully solve the original problem. These are usually medium or hard problems, as breaking down a problem into subproblems may not be obvious and may require some critical observation. These problems are also implementation-heavy, meaning the solution code is often big and complex, which makes it error-prone.

Asking yourself the following questions will help you determine whether a problem is a reversal subproblem pattern problem or not.

Example

Let's consider an example problem and see how to break it down into smaller subproblems that can be solved using the reversal algorithm to understand it better.

Problem statement: Given a linked list, reverse the list in groups of K in-place. If the last group in the list does not have K nodes, don't reverse it.

Consider the following example with k = 3 for a linked list of size 7.

Linked list reversal solution

Let's ask ourselves the questions we listed above to identify if we can reduce this problem to the two-pointer pattern problem.

The critical observation here is that reversing a group of size k is the same as reversing a part of the linked list between start and end. We traverse the linked list k nodes at a time and reverse each group as we go. We initialize a variable groups with the number of k-groups (length / k) to reverse, truncating the fractional part as the number of k groups will always be a whole number. We use groups to iterate, reversing a k-group in each iteration. 

We use two reference variables start and end to denote the boundary of a k-group that we need to reverse and a variable leftBound to hold the node before start that is used to correctly connect the head of the reversed segment to the list.

We initialize start and end with the head of the list and iterate k-1 times using end to find the end of the first k-group. We initialize leftBound with null for the first k-group, as there is no node before the head of the list.

After reversing the first k-group, we need to update the head of the list, as the previous end node will be the new head of the list.

Similarly, after reversing the first k-group, the previous start and the node after it would be the leftBound and start for the next k-group respectively.

We repeat the process to find the end of the next segment and reverse the list between start and end and for all the subsequent k-group reversals, we use leftBound to connect the reversed head of the segment back to the list. At the end of all iterations, all the k-groups in the list are reversed in place. The complete execution of the linked list reversal solution is given below.

The implementation of the reversal algorithm solution is given below, where we create a reverse function to reverse segments between start and end.  We also create helper functions to find the length of the list  two helper functions to find the length of a linked list and reverse the list between start and end to keep the implementation simple and modular.

The process above summarizes how we can identify a problem that can be broken down into smaller subproblems solvable by the reversal algorithm.

Example problems

Most problems in this category are medium or hard problems, as subproblems may not be directly identifiable. Also, the implementation may be complex and require creating different functions, which can be error-prone. Below is a list of problems that fall under the reversal subproblem pattern.

• Pairwise swap
• Reverse K-segments
• Reverse increasing groups
• Reverse alternate segments

We will now solve these problems to get a better understanding of breaking down a problem into subproblems solvable by the reversal algorithm.