Two Pointers Algorithm
Two pointers algorithm is a widely used technique in computer programming for solving various problems that involve traversing data structures such as arrays and linked lists. The key idea behind the two pointers algorithm is to maintain two pointers that traverse the data structure in opposite or same directions, depending on the problem at hand, and update the pointers based on specific conditions until a desired result is found or the end of the data structure is reached.
One common use case of the two pointers algorithm is when the data structure can be traversed in both directions and the goal is to find a pair of elements that match a certain condition. For example, finding two elements in an array that add up to a target value. In this case, the two pointers start at the beginning and end of the array and move towards the middle while updating the pointers based on the sum of the elements they point to being less than, equal to, or greater than the target value.
#include <stdio.h>
#include <stdlib.h>
void findPair(int arr[], int n, int target) {
int start = 0;
int end = n - 1;
while (start < end) {
int sum = arr[start] + arr[end];
if (sum == target) {
printf("Pair found at index %d and %d\n", start, end);
return;
} else if (sum < target) {
start++;
} else {
end--;
}
}
printf("Pair not found\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 6};
int target = 6;
int n = sizeof(arr) / sizeof(arr[0]);
findPair(arr, n, target);
return 0;
}
Another use case of the two pointers algorithm is when the goal is to find the length of a sub-array or sub-string that satisfies certain conditions. This is known as the sliding window approach, where the two pointers both start at the same position and move in the same direction while updating the pointers based on the conditions of the elements within the current window. For example, finding the length of the longest sub-string with non-repeating characters.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int lengthOfLongestSubstring(char* s) {
int n = strlen(s);
int start = 0;
int end = 0;
int maxLength = 0;
int charCount[256] = {0};
while (end < n) {
if (charCount[s[end]] == 0) {
charCount[s[end]]++;
end++;
maxLength = fmax(maxLength, end - start);
} else {
charCount[s[start]]--;
start++;
}
}
return maxLength;
}
int main() {
char s[] = "abcabcbb";
int length = lengthOfLongestSubstring(s);
printf("Length of the longest substring with non-repeating characters: %d\n", length);
return 0;
}
The two pointers algorithm is a flexible and efficient technique for solving various problems related to arrays and linked lists. Whether the two pointers move in opposite or same directions, the key is to use the pointers to traverse the data structure and update them based on specific conditions until the desired result is found. By utilizing the two pointers algorithm, developers can quickly and effectively solve a wide range of problems.