what is 2 pointer method in array? explain with example
The Two Pointer Method is a common technique used in algorithm design, particularly for problems involving arrays or linked lists. It utilizes two pointers that move through the data structure to solve the problem efficiently. This technique can often reduce the time complexity to O(n) in problems where a brute-force approach might take O(n^2) or worse.
### Key Characteristics of the Two Pointer Method:
1. **Multiple Pointers**: You maintain two pointers (or more) that traverse the array/list, allowing you to manage and compare elements effectively.
2. **Linear Traversal**: Typically, each pointer will move through the array once, leading to a linear time complexity.
3. **Problem Specific**: The specific problem will dictate how the pointers move, whether they start from the same point, opposite ends, or with some fixed distance apart.
### Example: Finding a Pair with a Given Sum
#### Problem Statement
Given a sorted array of integers, find two numbers such that they add up to a specific target sum.
#### Example Input
```plaintext
Array: [1, 2, 3, 4, 6]
Target Sum: 6
```
#### Solution Using the Two Pointer Method
1. **Initialize Two Pointers**: Start one pointer at the beginning (left) of the array and the other at the end (right).
2. **Iterate Until Pointers Meet**: Check the sum of the elements at both pointers.
- If the sum is equal to the target, return the numbers.
- If the sum is less than the target, move the left pointer to the right to increase the sum.
- If the sum is greater than the target, move the right pointer to the left to decrease the sum.
#### Implementation
Here’s a simple implementation in Python:
```python
def find_pair_with_sum(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return (arr[left], arr[right]) # Found the pair
elif current_sum < target:
left += 1 # Move left pointer to the right to increase the sum
else:
right -= 1 # Move right pointer to the left to decrease the sum
return None # No pair found
# Example usage
arr = [1, 2, 3, 4, 6]
target = 6
result = find_pair_with_sum(arr, target)
print(result) # Output: (2, 4)
```
### Explanation of the Code:
- We initialize two pointers, `left` at the start and `right` at the end of the array.
- In each iteration:
- We calculate the `current_sum` of elements at both pointers.
- If it matches the `target`, we return the pair.
- If it’s less than the `target`, we move the left pointer to the right (since the array is sorted, this will increase the sum).
- If it’s greater than the `target`, we move the right pointer to the left (this will decrease the sum).
- The process continues until the pointers meet, ensuring we check all possible pairs without redundant checks.
The Two Pointer Method is powerful and often the preferred approach for many array-related problems due to its efficiency and simplicity.