Problem Statement
Given a sorted array of integers, find a pair of elements that sum up to a given target value.
Sample Test Case
Input
- Array: [1, 2, 4, 7, 11, 15]
- Target: 9
Output
Approaches
Brute Force Approach
Idea
Check every possible pair of elements in the array to see if their sum is equal to the target.
Steps
- Use two nested loops.
- In the outer loop, pick an element.
- In the inner loop, check if the sum of the selected element and any other element equals the target.
Time Complexity
- O(n^2), where n is the number of elements in the array.
Space Complexity
- O(1), since no additional data structures are used.
Example Code (JavaScript)
Dry Run
- Input: arr = [1, 2, 4, 7, 11, 15], target = 9
- Outer loop picks 1, inner loop checks pairs (1, 2), (1, 4), (1, 7)...
- Eventually, (2, 7) is found, returning the pair.
Efficient Approach (Two Pointer Technique)
Idea
Since the array is sorted, use two pointers starting at the beginning and end of the array and move them towards each other.
Steps
- Start with two pointers, one at the beginning (
low
) and one at the end (high
) of the array.
- Calculate the sum of the elements at the pointers.
- If the sum equals the target, return the pair.
- If the sum is less than the target, move the
low
pointer to the right.
- If the sum is greater than the target, move the
high
pointer to the left.
- Repeat until the pointers meet.
Time Complexity
- O(n), where n is the number of elements in the array.
Space Complexity
- O(1), since no additional data structures are used.
Example Code (JavaScript)
Dry Run
- Input: arr = [1, 2, 4, 7, 11, 15], target = 9
- Initial pointers at (1, 15), sum = 16, move the
high
pointer left.
- Next pair (1, 11), sum = 12, move the
high
pointer left.
- Next pair (1, 7), sum = 8, move the
low
pointer right.
- Next pair (2, 7), sum = 9, return the pair (2, 7).
Example Test Cases
-
Input: arr = [1, 2, 3, 4, 5], target = 9
Output: [4, 5]
-
Input: arr = [1, 3, 5, 7, 9], target = 10
Output: [1, 9]
-
Input: arr = [-1, 0, 1, 2], target = 1
Output: [0, 1]
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n^2)
- Space Complexity: O(1)
Efficient Approach
- Time Complexity: O(n)
- Space Complexity: O(1)
Conclusion
The brute force approach checks all possible pairs and works with a time complexity of O(n^2). The efficient two-pointer technique leverages the sorted nature of the array, achieving a time complexity of O(n) with a space complexity of O(1). For larger datasets, the efficient approach is highly recommended.