Home Two Sum II - Input Array Is Sorted
Post
Cancel

Two Sum II - Input Array Is Sorted

Links

Go to my solution
Go to the question on LeetCode

My Thoughts

What Went Well
I knew to use the two-pointer method because the list was sorted.

What I Learned
I further solidified the two-pointer method in my brain.

Algorithm Description

Two Pointer Algorithm - If a list is sorted and we place a pointer at the extreme values (max and min), we can iterate one pointer at a time to approach the solution.

Binary Search - A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.

Visual Examples
The two-pointer algorithm being performed on a list, click to view

Binary search being performed on an array that contains the target, click to view

Binary search being performed on an array that does not contain the target, click to view

Solution Statistics

Time Spent Coding
5 minutes

Time Complexity
O(n) - In the worst case, the target indices are near the middle, resulting in the O(n) time complexity because almost all indices will be visited.

Space Complexity
O(1) - We only need to declare two new variables, and the number of variables does not depend on the number of elements in the list (n), resulting in the O(1) space complexity.

Runtime Beats
79.62% of other submissions

Memory Beats
80.90% of other sumbissions

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        p0 = 0
        p1 = len(numbers) - 1

        while p1 > p0:
            # If the elements at the indices sum to the target
            if numbers[p0] + numbers[p1] == target:
                # Return them, but add one 
                # (This is a special constraint that only applies to this problem)
                return [p0+1,p1+1]

            # If the number is greater than the target, then we know if we decrement
            # p1 we will get a smaller value, there for inching closer to the target
            if numbers[p0] + numbers[p1] > target:
                p1 -=1

            # The same principle applies here, except the sum is smaller than the target
            # and incrementing p0 gets us a larger value
            else:
                p0 +=1
This post is licensed under CC BY 4.0 by the author.

Two Sum

3Sum