|
| 1 | +#Two Pointer Algorithm |
| 2 | + |
| 3 | +##Overview |
| 4 | + |
| 5 | +The Two Pointer Algorithm is a technique used for efficiently solving problems with linear data structures like arrays or linked lists. It involves using two pointers to traverse the data structure and perform operations based on certain conditions. |
| 6 | + |
| 7 | +##Basic Idea |
| 8 | + |
| 9 | +The basic idea behind the Two Pointer Algorithm is to maintain two pointers that traverse the data structure in a way that reduces the time complexity. The pointers move towards each other or in a specific pattern based on the problem requirements. |
| 10 | + |
| 11 | +##Algorithm Steps |
| 12 | + |
| 13 | +1.**Initialize Pointers:** |
| 14 | +- Initialize two pointers, usually at the beginning or end of the data structure. |
| 15 | + |
| 16 | +2.**Move Pointers:** |
| 17 | +- Move the pointers towards each other, closer or farther based on the problem requirements. |
| 18 | +- Update pointers based on specific conditions. |
| 19 | + |
| 20 | +3.**Check Conditions:** |
| 21 | +- Check conditions at each step to determine if the solution is found or if the pointers need to be adjusted. |
| 22 | + |
| 23 | +4.**Repeat:** |
| 24 | +- Repeat steps 2 and 3 until the pointers meet or fulfill the problem requirements. |
| 25 | + |
| 26 | +##Common Use Cases |
| 27 | + |
| 28 | +1.**Array Sum/Pair Sum:** |
| 29 | +- Finding pairs in a sorted/unsorted array that sum up to a given target. |
| 30 | + |
| 31 | +2.**Search in a Sorted Array:** |
| 32 | +- Searching for a target element efficiently in a sorted array. |
| 33 | + |
| 34 | +3.**Palindrome Check:** |
| 35 | +- Checking if a given string or array is a palindrome. |
| 36 | + |
| 37 | +4.**Trapping Rain Water:** |
| 38 | +- Calculating the amount of water that can be trapped between bars in an elevation map. |
| 39 | + |
| 40 | +##Example |
| 41 | + |
| 42 | +###Two Sum Problem |
| 43 | + |
| 44 | +``` |
| 45 | +int main() { |
| 46 | + // Example input vector |
| 47 | + std::vector<int> nums = {2, 7, 11, 15}; |
| 48 | + int target = 9; |
| 49 | +
|
| 50 | + // Sorting the input vector |
| 51 | + std::sort(nums.begin(), nums.end()); |
| 52 | +
|
| 53 | + // Initializing two pointers |
| 54 | + int left = 0; |
| 55 | + int right = nums.size() - 1; |
| 56 | +
|
| 57 | + // Two Pointer Algorithm |
| 58 | + while (left < right) { |
| 59 | + int currentSum = nums[left] + nums[right]; |
| 60 | +
|
| 61 | + if (currentSum == target) { |
| 62 | + // Solution found |
| 63 | + std::cout << "Pair found: [" << nums[left] << ", " << nums[right] << "]" << std::endl; |
| 64 | + return 0; |
| 65 | + } else if (currentSum < target) { |
| 66 | + // Move left pointer to the right |
| 67 | + ++left; |
| 68 | + } else { |
| 69 | + // Move right pointer to the left |
| 70 | + --right; |
| 71 | + } |
| 72 | + } |
| 73 | +
|
| 74 | + // No solution found |
| 75 | + std::cout << "No pair found." << std::endl; |
| 76 | +
|
| 77 | + return 0; |
| 78 | +} |
| 79 | +
|
| 80 | +``` |