Fast and Slow Pointer

We can extend two pointers approach and use them as fast and slow pointer as well to solve more complex problems. In slow and fast pointer, we mostly extend slow pointer by 1 index and fast pointer by 2 indexes. This algorithm is known as Floyd’s Cycle Detection Algorithm. Let us look at a few of the solutions to better understand this algorithm.

TO CHECK IF THE TAIL OF THE LINKED LIST IS POINTING BACK TO ANY ELEMENT IN THE LINKED LIST

The fast-slow pointer can help us figure out if the tail of the linked list is pointing to any of the elements in the linked list. We will assign both the slow and fast pointers to the head of the linked list and will increment the slow pointer by 1 and the fast pointer by 2 in every iteration. If the fast pointer matches the slow pointer, that means the fast pointer re-iterated and the tail is not pointing to null. In case the tail is pointing to null and since the fast pointer was getting increase by 2 and the slow pointer was getting increased by 1. The fast and slow pointer should never point to the same element in the linked lsit.

TO FIND THE MIDDLE ELEMENT OF THE LINKED LIST

We can make use of this algorithm to find the middle element of the linked list quickly. We can start by pointer both of our pointer to the head of the linked list and we will move the slow pointer by 1 index and fast pointer by 2 indexes. We need to continue this until the fast pointer points to null or the linked list's last element. We can understand this flow with the help of the below diagram:

If we will observe the flow, by the time the fast pointer reaches the end (in case an odd number of elements are present in the linked list) or points to null (in case of even number of elements are present in the linked list), the slow pointer reached the middle element.

TO CHECK IF THE LINKED LIST IS PALINDROME

We can make use of the fast-slow pointer to check if the linked list is palindrome or not. We can follow the below flow to check the palindrome:

1. Make use of a fast-slow pointer to iterate the slow pointer until the linked list's middle element.

2. While iterating, the slow pointer till the middle element, we will be reversing the linked list.

3. Once the linked list is reversed, we will be having two different links linked list just need to place our pointers again to the head of both the pointers and compare if the elements are equal or not. If they are equal, then it is a palindrome.

Two reverse a linked list, we need to use 3 pointers, which is discussed in detail in our blog Reverse Linked List. Since we need to reverse only half of the linked list, we will be adding one additional pointer to figure out the middle element. Hence, in this case, we will be using four-pointers. Two of them will be used to figure out the middle element and the other two will be used to reverse the linked list:

Next, we will be assigning the slow and fast pointer to the head of the linked list and previous and next pointers as null for start. Next, we will follow the below logic until we iterate till the middle of the linked list to iterate the first half of the linked list:

1 2 3 4 5 6 7 8 9

while(fast != null && fast.next != null){ fast = fast.next.next; next = slow.next; slow.next = previous; previous = slow; slow = next; }

Let us say that the linked list is 1->2->2->1, after the first iteration of the while loop:
- The fast pointer will be at the 3rd element of the linked list.  (Image 2)

- The next pointer will be at the 2nd element of the linked list. (Image 3)

- The slow.next will become null i.e. the first element will stop pointing to the second element. This is required as we need to reverse the point which will be completed in the second iteration of the loop. (Image 4)

- The previous pointer will be at the 1st element of the linked list. (Image 5)

- The slow pointer will be at the second element, the same as the next pointer. (Image 6)

After the second iteration is completed, we will reach out middle element and the first half of the linked list will be reversed.

Post the second iteration of the while loop:
- The fast pointer will be null, making sure it will be the last iteration. (Image 1)

- The next pointer will move to the 3rd element. (Image 2)

- The slow.next will point to the previous pointer element i.e. the first element in this case. At this step, the linking is reversed. (Image 3)

- The previous pointer will then move to the second element. (Image 4)

- The slow pointer will move to the 3rd element of the linked list (Image 5)

This will help us divide the linked list into two separate linked lists. Next, we need to get two pointers to point to the head of these separate linked lists.

1 2 3 4 5 6 7 8 9

//Initiating Fast pointer to second linked list head. if(fast == null){ fast = slow; } else { fast = slow.next; } //Initiating Slow pointer to first linked list head. slow = previous;

The above logic will help us to get the head of both the linked list. For the second linked list, we need to check if fast is null or not.
If the fast pointer is null, we can assign the slow pointer reference to the fast pointer directly as it will be the case of even elements in the complete linked list. Hence, the slow pointer will be referring to (number of elements/2 -1).  
In case fast is not null, it explains that the fast pointer is referring to the last element of the linked list which means that the number of elements in the linked list is odd and in this case, the slow pointer is exactly pointing to the middle element. Hence, we can assign slow.next to fast pointer as we need not check the middle element for palindrome in case of odd elements linked list.

Once we have the separate linked list, we can simply iterate it using the below logic and checking each value. If any of the values are incorrect, the linked list is not a palindrome.

1 2 3 4 5 6 7 8 9

while(slow != null && fast != null){ if(slow.val != fast.val){ return false; } slow = slow.next; fast = fast.next; } return true;

Read More

Two Pointers

Two Pointers is a technique of solving problems of linear data structure, especially arrays. It helps to solve problems with lesser time complexity and space complexity and simplifies our code. Let us have a look at a few of the basic problems solved using two-pointers to understand the concept better. Ideally, we point to the first and last index of an array or the first and second index of an array to iterate the array and then move the pointers accordingly. The approach followed in the below problems might help us in solving more complex problems with an easier approach.

TO FIND A SORTED ARRAY OF SQUARES OF A SORTED ARRAY

Let us assume that we need to figure out an array of squares of a sorted array in increasing order. For Example, we need to find a sorted array in increasing order for squares of the element of [-5,-3,-1,0,3,4,6]. 

One way to achieve this is to iterate every member of the given array, square it and store it in a result array. Next, we can sort the result array. If we follow this approach, the time complexity will include the time to iterate the array and the time to sort it. 

Two pointers can help us in this case to minimize the time complexity. Let's declare two integers to point to the first and last index of an array as shown in the below figure. We can then declare a result array and iterate it from last to end and for each iteration of the result array; we can check the square of the start and end pointer. Whichever, square value is greater can be filled in the result array and the pointer can be decreased if it was the end pointer or can be increased if it was the start pointer. This will help us in getting the desired result.

In the above figure, the pointers are placed at -5 and 6 and an empty result array is declared. Next, the square value of both the pointers is computed and it is determined that 36 Is bigger than 25. Hence, 36 is stored in the result array and the end pointer is decreased by 1. 

In the next step, we computed the square value of both the pointers again and determined that 25 is bigger than 16. Hence, 16 is placed in the result array and the start pointer is incremented by 1. 

Once we are done iterating all the elements of the result array, we will get the desired sorted result.

TO MOVE ALL THE ENTRIES OF A PARTICULAR VALUE AT THE END OF THE ARRAY

Next, we will try to move all the entries of a particular value to the end of the array. Let us try to move all the "1" from the array [1,1,0,3,2,8,1]. 

An easier way to solve this problem is to create a new array of the same size and insert all the non "1" entries from the original array to the new array by iterating the original array. Once the iteration is completed, we can add 1 to the remaining indexes of the new array to get the desired output.

An efficient way to solve this problem is via the two-pointers approach. Let us have a look at the diagram below to understand the execution flow:

To solve this problem, we can initiate two pointers at the start of the array only, and can execute a loop until the second pointer is less than the size of the array and follow the below logic:

• If the second pointer value is "1", increment the second pointer and continue the loop.
• If the second pointer value is not "1", check the first pointer value and second pointer value. If they are not the same, swap the values.
• Increment both first and second pointer.

This approach will help us save some space complexity as no new array creation will be required and is an efficient way to solve the problem.

HOW TO REVERSE A STRING USING TWO POINTERS

Let's try to reverse a string. The string is nothing but an array of char, we can apply the two-pointers approach to simplify the problem. Let's assume that we have been given a char array ['A','U','T','O','P','A','C','E'] and we need to get reverse the array and obtain ['E','C','A','P','O','T','U','A'].

Let us declare a start pointer and an end pointer in this case. We can run a loop until the start pointer is less than the end pointer and can follow the below logic:

• Swap the start pointer and end pointer values.
• Increase the start pointer by 1 and decrease the end pointer by 1.

The below diagram shows the complete execution for this problem:

The two pointers can be extended to be used as a fast-slow pointer which is explained in detail in our blog Fast-Slow Pointers.

Read More