Introduction
When working with sorted arrays, a common challenge arises: discovering two elements that sum up to a specific target value. In this task, we are given a sorted array and a target sum, and our goal is to identify two numbers from the array that add up to this target. An interesting constraint is that the solution indices should be 1-based instead of the typical 0-based indexing.
The Initial Approach
The straightforward method might involve examining every possible pair of elements. Starting with the first element, we test its combination with all subsequent elements to find a match with the target. Consider a scenario where the target is 9, and we explore sums with the initial few numbers:
- 1 + 3 = 4
- 1 + 4 = 5
- 1 + 5 = 6
- 1 + 7 = 8
- 1 + 10 = 11 (greater than 9)
Upon reaching a sum greater than the target, further comparisons with smaller elements stagnate as the rest will exceed the target due to the sorted nature of the array.
Exploring Combinations
Continuing this approach, check combinations beginning with 3:
- 3 + 4 = 7
- 3 + 5 = 8
- 3 + 7 = 10 (greater than 9)
From here, a pattern emerges: after exceeding the target, subsequent elements will surpass it as well. Continuing with another set:
- 4 + 5 = 9 (perfect match)
This brute force technique navigates the entire array, resulting in a time complexity of O(N²), which can be inefficient.
Optimizing with Two Pointers
Utilizing the fact that the array is sorted, a more efficient strategy involves two pointers: one at the array's start (left) and one at the end (right). The pointers help to dynamically adjust the sum towards the target:
graph TD
A["Start"] --> B["Initialize left and right pointers"]
B --> C["Compute sum of elements at pointers"]
C --> D{"Is sum = target?"}
D -->|Yes| E["Return 1-based indices"]
D -->|No| F{"Is sum > target?"}
F -->|Yes| G["Move right pointer left"]
F -->|No| H["Move left pointer right"]
E --> I["End"]
G --> C
H --> C
I
%% Style: white arrows, white node borders and labels
linkStyle default stroke:#ffffff,stroke-width:2px
style B fill:transparent,stroke:#ffffff,color:#ffffff
style C fill:transparent,stroke:#ffffff,color:#ffffff
style D fill:transparent,stroke:#ffffff,color:#ffffff
style E fill:transparent,stroke:#ffffff,color:#ffffff
style F fill:transparent,stroke:#ffffff,color:#ffffff
style G fill:transparent,stroke:#ffffff,color:#ffffff
style H fill:transparent,stroke:#ffffff,color:#ffffff
style I fill:transparent,stroke:#ffffff,color:#ffffff
Implementing the Solution
The algorithm efficiently reduces unnecessary checks by methodically shifting pointers based on the sum's comparison with the target. Initially, both pointers are placed at opposite ends of the array.
By iterating through the array:
- If the current sum exceeds the target, shift the right pointer one position to the left.
- If the sum is below the target, move the left pointer one position to the right.
- When the target sum is found, output the indices, adjusting them for 1-based indexing.
This two-pointer technique refines the problem-solving process to a linear time complexity of O(N).