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