3Sum - Leetcode 15 - 2 Pointers (Python)

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[khndokarrashid]

Love your videos man! im currently a data analyst trying to transfer over to software engineering and this is helping me a lot!

[abbasfadhil]

Naming the function three sum is wild ☠️

[rijumondal]

there is a better solution I guess, why using a set to store unique list, we can just move the pointers till we found a new int in a sorted array, this will basically cancel the possiblity of taking the duplicate without using the extra space

class Solution {
public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> ans = new ArrayList<>();

int n = nums.length;

Arrays.sort(nums);

for(int i = 0 ; i < n-1 ; i++){

int j = i+1;

if (i > 0 && nums[i] == nums[i - 1]) continue;

int k = n-1;

while(j < k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0){
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
while(j < k && nums[j] == nums[j+1]){
j++;
}
while( j < k && nums[k] == nums[k-1]){
k--;
}
j++;
k--;
}
else if(sum < 0){
j++;
}
else{
k--;
}
}



}


return ans;

}
}

[cs_peter_lorenz]

First of all thanks for your videos and you explain very well. :)

I may have found a limitation of your solution: Your hashmap only works by the assumption that there are maximum duplicates of the same number. Is that a requirement for the this leetcode questions?
What is about, if you have [-1, 0, 1, 2, -1, -4, -1] ? Here would be 3 times -1. The indexing would be become wrong.

[zdzisawdyrman]

Well... everything fine apart for the face that this solutions gets: "Time limit exceeded"

[Glitzwhisker]

Leet code no longer accepts tuples in the answer

[newbiedb]

At 5:21, can you explain more about hashable and mutable in Set?

[jyotiaggarwal]

Hi,

I used your solution for Python3 and after submitting, it is showing Time Limit exceeded.
How can I improvise it to resolve this issue as I see we using two pointer approach here with hashMap simultaneously which costs O(N*2) complexity but sorting and storing in set increases its complexity.could you please help

[NitinKumar-qstw]

Hey Greg! unfortunately time limit exceeded for last test case on Leetcode. 312/313 test cases passed.

[santanu_barua]

Java Solution for this:

public List<List<Integer>> threeSum(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i< nums.length; i++) {
map.put(nums[i], i);
}
Set<List<Integer>> result = new HashSet<>();
for (int i = 0; i< nums.length;i++) {
for (int j = i+1; j< nums.length; j++) {
int desired = -nums[i] - nums[j];

if (map.containsKey(desired) && map.get(desired)!= i && map.get(desired)!=j) {
List<Integer> triplet = Arrays.asList(nums[i], nums[j], desired);
Collections.sort(triplet);
result.add(triplet);
}
}
}
return new ArrayList<>(result);
}

[saitejasai]

If we have a duplicate in nums, we are replacing the value of corresponding duplicate (i.e, . new index of duplicate) in dict. Doesn't this affect the code? I watch your videos. You explain well. thank you!

[chriszhu]

🤔anybody else getting this? `{(-1, 0, 1), (-1, -1, 2)} is not valid value for the expected return type list<list<integer>>`

[lakshayjain]

Great logic
But why this c++ code is storing similar strings

vector<vector<int>> threeSum(vector<int>& nums) {
unordered_map<int, int> map;
int i, j, n=nums.size();
vector<vector<int>> ans;

sort(nums.begin(), nums.end());
for(i=0;i<n;i++)
{
map[nums[i]]=i;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
int tmp=-nums[i]-nums[j];

{
vector<int> sa;
sa.push_back(nums[i]);
sa.push_back(nums[j]);
sa.push_back(tmp);
sort(sa.begin(), sa.end());
ans.push_back(sa);
}
}
}
return ans;
}

[samspeaks-hkvp]

shouldn’t time complexity more than o(n3) cause we sorting in the inner loop?

[DariusD]

What is considered a "duplicate triplet"? All value permutations of a triplet are duplicates? e.g. [2, -1, -1] or [-1, 2, -1]?

[antipainK]

Using a set feels like cheating here...

[ThsHunt]

why do the step of filling hashset doesnt count towards the time

[onlywrestling]

It gives TLE,
only 312/313 test cases are passed

[jagrat]

getting Time Limit Exceeded using this method, dont know why. Even running ur code does the same