What is the Two Pointers Technique?
The strategy known as the Two-Pointer Technique initiates by manipulating two pointers located at distinct positions within the array. One pointer advances towards the other, while the second pointer moves in the same direction under certain specified conditions. This method proves to be highly effective in resolving disparity-related issues by appropriately adjusting the pointers.
Understanding the Two-Pointer Technique:
The Pointer Methodology maintains its significance by employing a pair of pointers to address issues effectively. Typically, these indicators traverse either an array or a linked list simultaneously from an initial position towards the solution. Its relevance becomes apparent when tasks involve searching, sorting, or managing data within arrays or intricate structures like linked lists.
Key Concepts:
- Initialization: If we have built two pointers, those pointing to the following, or the end of the array, or maybe both of them if we are handling a linked list.
- Traversal: The directions containing a conditionals and rendezvous should be brought to the notice and updated after that. Conversely, it might be the one that perfectly fits the requirements of the current occupation.
- Condition Checking: At a definite moment, you have to fix certain restrictions and then compare them to the limit of the given problem. This is the area where the pointers-which players carry-are placed dependently with the positions they have in the two-dimensional space.
- Termination: Define the rule of termination for pointers in the pointer subroutine. In this case, it is better to have an algorithm of finishing both pointers at the same time or with one of them at the end of the array of the linked lits.
Several common use cases of the Two Pointers Technique are as follows:
- Finding Pairs: Using two markers, it is possible to locate in the sequence the numbers that add up, or subtract, to specific sums or combos.
- Searching Subarrays: The operation provides a pretty convenient method to find sequence parts of different sizes whose sum is some value or the length of a sequence is equal to some value.
- Removing Duplicates: Using a pointer, the process is efficient as the scanning phase works by incrementing one pointer while removing element that has been visited by the other pointer. • Checking Palindromes: We will determine if the string is a palindrome (or not).
Implementation in C:
Program to implement the two pointer technique.
Example 1: Finding a Pair with Given Sum
#include <stdio.h>
void findPair(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == target) {
printf("Pair found: (%d, %d)\n", arr[left], arr[right]);
return;
} else if (currentSum < target) {
left++;
} else {
right--;
}
}
printf("No pair found with the given sum.\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int target = 8;
int size = sizeof(arr) / sizeof(arr[0]);
findPair(arr, size, target);
return 0;
}
Output:
Pair found: (2, 6)
Explanation:
- Here the first function would be findPair which will determine if two input numbers sum to any target value you provide. This function is designed to take three parameters: arr = the input array already in place, consisting of nothing but integers, size = the array size and target = sum of the pair we are to find. Knowing the pointers in this getValue function, it initializes the memory areas. Initially, the left (left=index 0) and right (right=size -1) will be directed towards the array.
- The second loop starts and will repeat until the lefLogic Practiceer is lower than the righLogic Practiceer at the end of the loop. The existing sum of those element placed at the left and righLogic Practiceers is retrieved and stored into the variable currentSum that is being used to regulate the structure of this loop.
- Now, we check conditions based on the value of currentSum:
- In such case, if we have determined that the value of currentSum is equal to our target sum, it makes us realize that we have indeed found a pair that sums up to the specific target value. This is a situation where the function gets the task accomplished and identifies the elements that constitute the pair (arr[left] and arr[right]) from the function.
- If the sum that we have so far is less than the target, then we require to increase the sum and we can do that by moving the lefLogic Practiceer to the next index of the array (increase left).
- The righLogic Practiceer will be decreased by one position (decrease right) if currentSum is higher than the target or, if we need to have fewer elements, the currentSum need not be assigned to its another neighbour (pick fewer elements).
Example 2: Removing Duplicates from Sorted Array
#include <stdio.h>
int removeDuplicates (int arr[], int size) {
if (size <= 1)
return size;
int i = 0;
for (int j = 1; j < size; j++) {
if (arr[j] != arr[i]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}
int main() {
int arr [] = {1, 1, 2, 2, 2, 3, 4, 5, 5};
int size = sizeof (arr) / sizeof(arr[0]);
size = removeDuplicates(arr, size);
printf("Array after removing duplicates:\n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Array after removing duplicates:
1 2 3 4 5
Explanation:
- In this particular case, the removeDuplicates function takes two parameters: the array arr and the length of the array size.
- It ensures that the array dimensions are 1 and less. It yields back the size of the identically recurring records.
- If there are at least two elements in the array, the function initializes two pointers: i,j . The first array item is the end o of the pointer i, and j is the beginning of the second item.
- Loop the the array element since the beginning of the second element (index 1) and ending at the last element.
- Inside the loop, it compares the element at the jth location with the element at the ith location.
- If the elements are different, the loop i is increased, and the element indexed at j is assigned the value of the element at index i, thus removing duplicates.
- After processing each element, the function returns i+1, which indicates the new length of the array with the duplicates removed.
- The main function defines an array arr where duplicates are present.
- The size of the array is calculated using the operator sizeof.
- The call of the removeDuplicates function removes duplicates from the array, and the size is stored in the size variable.
- After that, the sorted array, without duplicates, is printed to the console.
Conclusion:
In summary, the C programming language employs the two-pointer method, an effective algorithm that focuses on manipulating two pointers traversing an array or linked list. This approach involves positioning the pointers to meet specified conditions and conducting searches for pairs, eliminating duplicate elements, and more. Example 1's algorithm is tailored to identify pairs with a specific sum, whereas Example 2 aims to extract all duplicate elements from a sorted array. By enhancing code readability, reducing time complexity, and optimizing memory usage through the elimination of redundant iterations, this technique proves to be a valuable asset.