703485. Pair with given sum in a sorted array
Here is the detailed Markdown blog post for the GeeksforGeeks problem "Pair with given sum in a sorted array":
Pair with given sum in a sorted array
Summary
Find all pairs in a sorted array that add up to a given sum. This problem involves using two-pointer technique, which is commonly used in arrays and linked lists.
Detailed Explanation
The problem requires you to find all pairs of elements in a sorted array that add up to a given target sum. The key concept involved here is the two-pointer technique. We can solve this problem by maintaining two pointers, one at the start of the array (left) and one at the end of the array (right).
Here's a step-by-step breakdown of the solution:
- Initialize two pointers, left and right, to the start and end of the array respectively.
- Calculate the sum of the elements at the left and right pointers.
- If the calculated sum is equal to the target sum, add this pair to our result list and move both pointers towards each other.
- If the calculated sum is less than the target sum, increment the left pointer to increase the sum.
- If the calculated sum is greater than the target sum, decrement the right pointer to decrease the sum.
- Repeat steps 2-5 until the left pointer meets the right pointer.
Here's a simple ASCII art diagram for better understanding:
+---------------+
| 1 2 |
| 3 4 |
| 5 6 |
| ... ... |
| n-1 n |
+---------------+
left right
Time complexity: O(n), where n is the size of the array. This is because we're scanning through the entire array once.
Space complexity: O(1), as we're not using any extra space that scales with the input size.
Optimized Solutions
Java
public class Main {
public static List<int[]> findPairs(int[] arr, int target) {
List<int[]> result = new ArrayList<>();
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
result.add(new int[]{arr[left], arr[right]});
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
}