Well, here, the brute force solution exists just as we saw in 1, you know.
And dictionary we cannot use in this case, because they say use only constant extra space.
So, for optimal solution, we will use two pointers,
The thinking goes like this,
Since the array is sorted, we will utilize that behaviour. If we have two pointers, starting at left and right ends, then in one pass, we come closer and closer, moving each one position at once, and we will have no surprises, as in, any surprise in element values, because the array is sorted.
So, we subtract right pointer value from target, and check if we get a positive number, if yes, we check the left pointer value.
If same, cool.
If greater, then there is surely no answer for this right pointer value and we must move the right pointer to left once.
If smaller, if we can move left pointer to right once, and compare again.
But moving left pointer to right seems problematic, what if the first value were to work with some other right pointer value, but no we’re already pass that left pointer value?
^The answer to this is that it can never happen. Because we’re moving L right, only if sum is less than target. So in that case, if this left value cannot reach the sum with the right value, how can this left value work with any smaller right value? So, there is no concern.
Btw, what I wrote above is subtract pattern. It is better to use sum pattern for two pointer solutions,
Like this,
sum = nums[L] + nums[R]
if sum == target -> answer
if sum < target -> L++
if sum > target -> R--
My idea, subtract pattern, was this,
needed = target - nums[R]
if nums[L] == needed -> answer
if nums[L] < needed -> L++
if nums[L] > needed -> R--
Both patterns can work and produce correct solution with two pointers, but sum pattern is preferred, because it is logically cleaner.
So, it will be time and constant space,
public class Solution {
public int[] TwoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.Length - 1;
while (left < right)
{
int sum = numbers[left] + numbers[right];
if (sum == target)
return new int[] {left + 1, right + 1}; // 1-based result
if (sum > target)
right--;
else
left++;
}
return Array.Empty<int>();
}
}