# Links

Go to the solution

Go to the question on LeetCode

# My Thoughts

**What I Learned**

I learned how to apply the two-pointer algorithm in a new way and use it in a more challenging problem.

**How I Can Improve**

Consistently studying my algorithms and improving my ability to recognize patterns in those problems will help me improve my coding skills.

# 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.

In this problem, we use the two-pointer algorithm on the elements between our ith + 1 element and the end of the list. So our search interval for the two pointer algorithm is [i+1:len(nums)]

**Visual Examples**

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

# Solution Statistics

**Time Complexity**

O(n^{2}) - We are iterating through each element in the list (n) when executing the for loop and then iterating through at worse n-2 elements during each iteration of that for loop, resulting in the O(n^{2}) time complexity. Since our logic results in a worse time complexity than sorting the list (O(n log n)), we ignore it and go with the larger complexity.

**Space Complexity**

O(1) - Python’s built-in sorting has an O(1) space complexity, and we are only creating four variables that do not depend on the size of the input list, resulting in the O(1) space complexity.

**Runtime Beats**

81.71% of other submissions

**Memory Beats**

76.26% 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
trip = []
# Sorting the list allows us to use the two pointer algorithm on the remaining
# elements after selecting the first element
nums.sort()
for i, n in enumerate(nums):
# To avoid duplicates and refine our time complexity, we can check these conditions
# Essentially skipping numbers we have already checked
if i > 0 and n == nums[i-1]:
continue
# Perform two sum with the target being 0
p0,p1 = i+1, len(nums) - 1
while p0 < p1:
# Assign the sum to tot and check its value
tot = nums[p0] + nums[p1] + n
if tot > 0:
p1 -=1
elif tot < 0:
p0 += 1
else:
trip.append([n,nums[p0],nums[p1]])
p0 +=1
# Another method to avoid duplicates and refine our time complexity
# Essentially skipping numbers we have already checked and
# ensuring we properly increment to the next element
while nums[p0] == nums[p0-1] and p0 < p1:
p0 += 1
return trip