A reference to an object is a pointer. In some circumstances, memory-mapped computer hardware or another value located in computer memory is the value that is stored in that object’s memory address. To put it another way, a variable with an array’s address is likewise a pointer. As an example, we estimated the size of the pointers in the C program. We will use variables in the two-pointer technique to point to various objects by employing pointers that contain object addresses. As a result, they are also known as pointers in this context. Nothing more than an advanced optimization of specific brute-force methods is the two-pointer technique. Instead of always sorting the data, it uses some sort of order to reduce the time complexity.
What is Two Pointer Technique?
Data Structures and Algorithms states, “the most effective techniques are simple and well-executed.” The two-pointer technique is one of those techniques.
Two pointers run through the data structure in the two-pointer pattern until one or both meet the required criteria.
The “two-pointer technique” only uses a small number of concepts, so don’t worry. Additionally, it is a simple approach that, when applied correctly, is extremely powerful.
As a result, many interviews have a tendency to be slightly biased towards inquiries made via this method. We’ll review the basic ideas in this post and provide various examples so you’ll know when and how to use the two-pointer technique.
The two-pointer technique is just what it says it is. To complete a certain operation, we employ two pointers.
Illustration
Example Ques of Two Pointers Technique
We will be presenting a two-pointer algorithm to show how operations are carried out in both methods and, secondarily, demonstrate how the two-pointer algorithm optimizes code via time complexities across all dynamic programming languages, including C++, Java, Python, and even JavaScript.
Using Loops
Method 1: Naïve Approach Below is the implementation:
C++
#include <iostream>
#include <algorithm>
using namespace std;
bool hasPairWithSum(int arr[], int size, int targetSum) {
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] + arr[j] == targetSum) {
return true;
}
}
}
return false;
}
int main() {
int numbers[] = {2, 3, 5, 8, 9, 10, 11};
int target = 17;
int size = sizeof(numbers) / sizeof(numbers[0]);
sort(numbers, numbers + size); // Sort the array
bool hasPair = hasPairWithSum(numbers, size, target);
if (hasPair) {
cout << "There is a pair with the sum " << target << " in the array." << endl;
} else {
cout << "No pair found with the sum " << target << " in the array." << endl;
}
return 0;
}
Output:
There is a pair with the sum 17 in the array.
Java
import java.util.*;
class FindPairWithSum {
public static void main(String[] args) {
int[] arr = { 2, 3, 5, 8, 9, 10, 11 };
int targetSum = 17;
boolean hasPair = hasPairWithSum(arr, targetSum);
if (hasPair) {
System.out.println("A pair with the given sum exists in the array.");
} else {
System.out.println("No pair with the given sum found in the array.");
}
}
private static boolean hasPairWithSum(int[] arr, int targetSum) {
Set<Integer> seenNumbers = new HashSet<>();
for (int num : arr) {
int complement = targetSum - num;
if (seenNumbers.contains(complement)) {
return true;
}
seenNumbers.add(num);
}
return false;
}
}
Output:
A pair with the given sum exists in the array.
Python
def find_pair_with_sum(arr, target_sum):
seen = set()
for num in arr:
complement = target_sum - num
if complement in seen:
return True
seen.add(num)
return False
# Driver code
arr = [2, 3, 5, 8, 9, 10, 11]
target_sum = 17
result = find_pair_with_sum(arr, target_sum)
if result:
print("A pair with the given sum exists.")
else:
print("No pair found with the given sum.")
Output:
A pair with the given sum exists.
Time Complexity: O(n2). Auxiliary Space: O(1)
Using Two Pointer Algorithm
Let’s now examine the two-pointer approach in action. We take two pointers, one for the first element in the array and the other for the end element, and we add the values stored at both points. To come closer to the sum, the left pointer is moved to the right if its sum is less than X, and the right pointer is moved to the left if its sum is more than X. Until we obtain the amount as X, we keep shifting the points.
The implementation is shown below:
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findPairWithSum(vector<int>& array, int size, int targetSum) {
int left = 0;
int right = size - 1;
while (left < right) {
int currentSum = array[left] + array[right];
if (currentSum == targetSum) {
return 1; // Pair found
} else if (currentSum < targetSum) {
left++;
} else {
right--;
}
}
return 0; // Pair not found
}
int main() {
// Array declaration
vector<int> numbers = {2, 3, 5, 8, 9, 10, 11};
// Target sum to search for
int targetSum = 17;
// Size of the array
int arraySize = numbers.size();
// Sorting the array before using the two-pointer technique
sort(numbers.begin(), numbers.end());
// Calling the function
cout << (findPairWithSum(numbers, arraySize, targetSum) ? "True" : "False");
return 0;
}
Output:
True
Java
import java.util.Arrays;
import java.util.List;
public class PairSumFinder {
// Two-pointer technique based solution to find
// if there is a pair in the given list with a given sum.
public static boolean hasPairWithSum(List<Integer> list, int sum) {
// Represents the first pointer
int left = 0;
// Represents the second pointer
int right = list.size() - 1;
while (left < right) {
// If we find a pair
if (list.get(left) + list.get(right) == sum)
return true;
// If the sum of elements at the current
// pointers is less, we move towards higher values by incrementing left
else if (list.get(left) + list.get(right) < sum)
left++;
// If the sum of elements at the current
// pointers is more, we move towards lower values by decrementing right
else
right--;
}
return false;
}
// Driver code
public static void main(String[] args) {
// Array declaration
List<Integer> numbers = Arrays.asList(2, 3, 5, 8, 9, 10, 11);
// Value to search
int targetSum = 17;
// Size of the array
int arraySize = numbers.size();
// The array should be sorted before using the
// two-pointer technique
numbers.sort(null);
// Function call
boolean hasPair = hasPairWithSum(numbers, targetSum);
System.out.println("Does the list have a pair with the sum " + targetSum + "? " + hasPair);
}
}
Output:
Does the list have a pair with the sum 17? True
Python
from typing import List
def has_pair_with_sum(arr: List[int], target_sum: int) -> bool:
left_ptr = 0
right_ptr = len(arr) - 1
while left_ptr < right_ptr:
current_sum = arr[left_ptr] + arr[right_ptr]
if current_sum == target_sum:
return True
elif current_sum < target_sum:
left_ptr += 1
else:
right_ptr -= 1
return False
if __name__ == "__main__":
input_array = [2, 3, 5, 8, 9, 10, 11]
target_value = 17
input_array.sort()
if has_pair_with_sum(input_array, target_value):
print("A pair with the sum exists.")
else:
print("No pair with the sum found.")
Output:
A pair with the sum exists.
Time Complexity: O(n log n) (As sort function is used) Auxiliary Space: O(1), since no extra space has been taken.
Complexity Analysis
The Two-Pointer algorithm operates linear time complexity O(N) for sorted arrays/lists. It uses two pointers to traverse the array from both ends simultaneously, reducing the search space. This algorithm efficiently solves problems involving sorted data and performs a single pass through the array, making it a highly optimized technique. However, unsorted data may require additional sorting operations, increasing the time complexity to O(N log N).
FAQs
Q. When should I use the Two-Pointer Algorithm?
A. You should consider using the Two-Pointer Algorithm when dealing with problems that involve searching for pairs of elements in an array, subarrays with specific characteristics (e.g., a target sum), or finding sequences that satisfy certain conditions. It’s especially handy when the array is sorted.
Q. What are the advantages of the Two-Pointer Algorithm?
A. The Two-Pointer Algorithm is efficient and often has a time complexity of O(n), making it faster than brute-force solutions. It’s also relatively easy to implement and doesn’t require additional data structures.
Q. Can the Two-Pointer Algorithm be applied to unsorted arrays?
A. While the Two-Pointer Algorithm is most commonly used with sorted arrays, it can also be adapted for use with unsorted arrays in some cases. However, it may require additional steps, such as sorting a copy of the array or using a hash table to track elements.
Q. What are some common problems solved using the Two-Pointer Algorithm?
A. The Two-Pointer Algorithm is used in a variety of problems, including finding pairs with a given sum, checking if an array is a palindrome, merging two sorted arrays, and finding the maximum subarray sum (Kadane’s Algorithm), among others.
Conclusion
In conclusion, the Two-Pointer Algorithm is a powerful and efficient technique in various programming and algorithmic scenarios. This algorithm is particularly useful when dealing with sorted arrays or lists and allows us to solve problems related to searching, finding pairs, or optimizing solutions with a time complexity of O(n) or O(n log n), depending on the specific problem.
- The Two-Pointer Algorithm involves using two pointers or indices that traverse the data structure, typically an array or list, in a coordinated manner.
- It is most effective when working with sorted data because the relative positions of the two pointers can be adjusted based on the comparison of elements.
- The algorithm’s efficiency stems from reducing the search space or solving the problem in linear time or logarithmic time.
- This technique is commonly used for finding pairs with a specific sum, determining if a triplet exists with a given sum, searching for a target element in a sorted array, and more.
- The time complexity of the Two-Pointer Algorithm depends on the specific problem but often results in efficient solutions compared to brute-force approaches.
