TwoSum11InputArraySorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
 

Constraints:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.



My Solution:

numbers = [2, 7, 11, 15]
target = 9
for i, j in enumerate(numbers): 
    left, right = 0, len(numbers) - 1 #again, we are using integers to represent indicies that we will plug in
    while left < right:
        pointersum = numbers[left] + numbers[right]
        if pointersum == target: #we are comparing to the target directly this time instead of trying to find the complement. this is where this problem differs from two sum
            print(left + 1, right + 1) #this problem is different in that we are returning non indexed but lengthed values, so add 1
        elif pointersum < target: #since we know the array is sorted, we increment left pointer index to the next element that we will eventually plugin to the numbers list to get the value when we find the value we are looking for
            left += 1
        else:   #we either have to increment left or decrement right, so if pointer sum is not equal to or smaller than target, and the input array is sorted from largest to smallest, we must decrement right to index into a smaller value in the next iteration
            right -= 1 
       
# IMPORTANT DISTINCTION: for line 45 - while left < right - WE NEED WHILE LEFT < RIGHT BECAUSE WITHOUT THIS CHECK, IT WOULD CROSS, AND KEEP GOING UNTIL IT TRIES TO ACCESS AND INDEX ON THE OPPOSITE SIDE OUT OF BOUNDS. THIS MAY NOT RESULT IN AN INFINITE LOOP. Not having while left < right might not lead to an infinite loop but just slower calculation times
# While left < right is perfectly optimized because it stops right before it starts checking duplicate sums, which would waste time as the left pointer would revisit an element that right pointer already visited and vice versa.
# While left < right is perfectly optimized to make the least amount of unnecessary comparisons. 


#7/21/24 refresher:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        res = []
        l, r = 0, len(numbers) - 1
        while l < r:
            if numbers[l] + numbers[r] == target:
                res = [l + 1, r + 1]
                return res
            elif numbers[l] + numbers[r] > target:
                r -= 1
            else:
                l += 1
        return res