3Sum - The Daily Programmer #323
video description
Date: 2022-03-14
Related videos
Comments and reviews: 9
Thomas
As most of the other comments said this is an n-3 solution. If an interviewer asked me a 3sum question I would say, -Well it could easily be solved by just using three for loops, to construct all triplets, then check as each is created if it sums to zero. if so add it to the list... but thatd be super inefficient so this is my solution...-
This is a leetcode medium problem, it cant be solved with 3 for loops (at least not solved correctly).
For those asking, there are two n-2 solutions for this:
The first one, (which is technically n-2 + n) would be construct all pairs, as youre constructing pairs, hash all of the numbers you see. Perhaps a dictionary where the key is the number, value is the amount of numbers you see. Then you loop through all pairs, and check your hash table to see if the value exists. to avoid duplicates, you would make the inner loop always start at the index of the outer loop. So youre really only searching from the outer index onward.
another solution, which is nlogn + n-2 is sort the array. Then loop through the array. For each loop, initalize a high and a low pointer, end of the array and the starting index + 1. If the triplet is greater than 0, you move the high pointer back. If the triplet is less than zero, you move the lower pointer forward, until you find a zero. Stick that in the array, and continue doing this until the low pointer is at the same index as the high, then break the loop and continue.
reply
As most of the other comments said this is an n-3 solution. If an interviewer asked me a 3sum question I would say, -Well it could easily be solved by just using three for loops, to construct all triplets, then check as each is created if it sums to zero. if so add it to the list... but thatd be super inefficient so this is my solution...-
This is a leetcode medium problem, it cant be solved with 3 for loops (at least not solved correctly).
For those asking, there are two n-2 solutions for this:
The first one, (which is technically n-2 + n) would be construct all pairs, as youre constructing pairs, hash all of the numbers you see. Perhaps a dictionary where the key is the number, value is the amount of numbers you see. Then you loop through all pairs, and check your hash table to see if the value exists. to avoid duplicates, you would make the inner loop always start at the index of the outer loop. So youre really only searching from the outer index onward.
another solution, which is nlogn + n-2 is sort the array. Then loop through the array. For each loop, initalize a high and a low pointer, end of the array and the starting index + 1. If the triplet is greater than 0, you move the high pointer back. If the triplet is less than zero, you move the lower pointer forward, until you find a zero. Stick that in the array, and continue doing this until the low pointer is at the same index as the high, then break the loop and continue.
reply
Khaled
Thank you very much for the video but if you look at the result you're printing you'll find for instance [9 -5 -4] & [-5 9 -4] and also [-5 -4 9] so, in my opinion this is still duplicates but different order. Isn't it?
reply
Thank you very much for the video but if you look at the result you're printing you'll find for instance [9 -5 -4] & [-5 9 -4] and also [-5 -4 9] so, in my opinion this is still duplicates but different order. Isn't it?
reply
beatlesfan
This is horrible. The O(n-3) solution is a brute-force stab. If you were to present this solution in a job interview, the interviewer will throw your solution out and ask you to come up with a better solution.
reply
This is horrible. The O(n-3) solution is a brute-force stab. If you were to present this solution in a job interview, the interviewer will throw your solution out and ask you to come up with a better solution.
reply
Sean
Wow. An O(n-3) solution is a surefire failure in an interview for a problem that can be solved in O(n-2). I'll be avoiding Free Code Camp in the future. Don't post coding videos with obviously suboptimal code.
reply
Wow. An O(n-3) solution is a surefire failure in an interview for a problem that can be solved in O(n-2). I'll be avoiding Free Code Camp in the future. Don't post coding videos with obviously suboptimal code.
reply
WikiPeoples
Um... your duplicate check doesn't work. It would not catch two equal sets such as this: [-1,0,1] , [1,0,-1] because your strings would not be equal, but the sets actually are equal.
reply
Um... your duplicate check doesn't work. It would not catch two equal sets such as this: [-1,0,1] , [1,0,-1] because your strings would not be equal, but the sets actually are equal.
reply
Christopher
This doesn't remove duplicates if you're returning an array. Most implementations of this question don't want arrays with rearranged similar numbers.
reply
This doesn't remove duplicates if you're returning an array. Most implementations of this question don't want arrays with rearranged similar numbers.
reply
Eva
I was expecting him to disapprove the O(n-3) approach and introduce a hashtable solution, but no.. -_- and it's surprising cuz it's a video by freeCodeCamp
reply
I was expecting him to disapprove the O(n-3) approach and introduce a hashtable solution, but no.. -_- and it's surprising cuz it's a video by freeCodeCamp
reply
Eric
This doesn't clean out duplicates anyway. His own code output shows two instances of 9, -4, -5. Needs a sort() in there somewhere to make that work.
reply
This doesn't clean out duplicates anyway. His own code output shows two instances of 9, -4, -5. Needs a sort() in there somewhere to make that work.
reply
The
This actually doesn't work. Given an array [0, 1, 2, 3, 4, 5]. 0, 3, and 5 would never be tested because i, j, and k are always adjacent.
reply
This actually doesn't work. Given an array [0, 1, 2, 3, 4, 5]. 0, 3, and 5 would never be tested because i, j, and k are always adjacent.
reply
Add a review, comment
Other channel videos
2:5:31
2:5:24
