Two pointers

"""
# two pointers - need the object to search over and the target
    # initialize the positions of the left and right pointers
    # while the left pointer is to the left of the right pointer
        # calculate what the potential match is with this combination
        # if you've found the target, return these pointers,
        # else if the target is to the left of the potential match, decrement the right pointer
        # else the target is to the right of the potential match, so increment the left pointer
    # if you reach here you haven't found a matching combination
"""
def two_sum(arr, target):
    l, r = 0, len(arr)-1
    while l < r:
        potential_match = arr[l] + arr[r]
        if potential_match == target:
            return [l, r]
        elif target < potential_match:
            r -= 1
        else:
            l += 1
    return []

# Example usage
arr = [2, 7, 11, 15]
target = 9
print(two_sum(arr, target))  # Output: [0, 1], because arr[0] + arr[1] = 2 + 7 = 9

"""
You might look at the pointer-moving logic and think, "Why do we just step to the right to decrease the current sum, when we could alternatively sometimes step to the left with the left pointer?" The answer is: because we only step inwards when we determine that a value at a given index *can't possibly* be part of the solution, because its partner doesn't exist on the other side of the array. We can draw this conclusion definitively because the array is sorted. So there's never a need to step back outwards on either side because those numbers have been definitively ruled out as being part of the solution.

So the essence of the two-pointer method is, "Can I rule out this index as being part of the solution? If so, step inwards."
"""