Hello, everyone! Today we will take a closer look at the “Two Pointer” algorithm and spend some time solving problems using this algorithm. The two-pointer technique is a very useful method for solving problems in data structures with a fixed size, such as arrays or lists. Each pointer is used to identify a position in the data structure, which helps reduce time complexity.
1. What is the Two Pointer Algorithm?
The two-pointer algorithm is a representative technique for efficiently solving problems when using two points simultaneously in a given array. It is mainly used to solve problems like sub-sums, maximum/minimum values, or to find pairs of data that satisfy specific conditions in sorted arrays.
The advantage of the two-pointer approach is that it allows you to obtain the necessary results by traversing the array only once with a single loop. This enables solving problems with a time complexity of O(n).
2. Problem Description
The problem we will solve this time is “Finding Ideal Pairs in an Integer Array.” Given an integer array arr and an integer K, find two numbers that sum up to K without a exclamation mark (!). Write a function that returns the indices of these two numbers. If such a pair does not exist, return -1.
Example Problem
- Input:
arr = [10, 15, 3, 7],K = 17 - Output:
(0, 2)// Indices are 0-based - Input:
arr = [10, 15, 3, 7],K = 20 - Output:
-1
3. Approach
We can use a mathematical approach to solve this problem. Since the sum of the two numbers needs to be K, the first pointer points to the start of the array, and the second pointer points to the end of the array. The sum of the values pointed to by the two pointers is then calculated and compared with K.
1. First, place the first pointer at the far left of the array and the second pointer at the far right.
2. Repeat until the two pointers cross each other:
- If the sum is equal to
K, return the indices of the two pointers. - If the sum is less than
K, move the first pointer to the right to increase the sum. - If the sum is greater than
K, move the second pointer to the left to decrease the sum.
3. If the two pointers cross each other without finding a pair, return -1.
4. Code Implementation
def two_sum(arr, K):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == K:
return (left, right) # Found a pair
elif current_sum < K:
left += 1 # Move left pointer to increase the sum
else:
right -= 1 # Move right pointer to decrease the sum
return -1 # Pair not found
5. Code Explanation
The above code is a function that uses the two-pointer technique to find a pair of indices such that their sum equals K. The left and right variables are used to start the pointers from both ends of the array.
First, in the while loop, we check if the two pointers are improving in direction. After calculating the sum of the current two values, if this value equals K, we return the corresponding indices. If not, we adjust the pointers based on the size of the sum and repeat.
6. Time Complexity Analysis
The time complexity of this algorithm is O(n). Since the two pointers start at both ends of the array, it ends with a single iteration, not requiring a full traversal of the array to satisfy the conditions. The space complexity is O(1), making it a very efficient method that uses only constant space.
7. Additional Examples
You can verify the correctness of the code through test cases.
print(two_sum([10, 15, 3, 7], 17)) # Output: (0, 2)
print(two_sum([10, 15, 3, 7], 20)) # Output: -1
print(two_sum([1, 2, 3, 4, 6], 10)) # Output: (3, 4)
8. Conclusion
Today we solved problems using the two-pointer technique. When solving Python algorithm problems, utilizing such techniques can save time and solve problems efficiently. Practice on various problems to accumulate more know-how. Next time, we will discuss dynamic programming. Thank you for your hard work today!