LeetCode 3Sum Solution Explained - Java

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[jonathanl]

I love how his submit history is all red

[tim]

if your are using c++

remember to cast size_t to signed integer

[leomonz]

nums[i] != nums[i-1] but in teh example they have two -1s, if you sort it then it is i and i-1

[Icix]

You can use a Set (HashSet) instead of a List to reduce the amount of edge cases you need to think about or amount of checks you need to do. A fair amount of your code just checking whether to skip duplicates and other edge cases, and these will be hard to remember in an interview setting. One thing I've noticed is if the result requires deduped anything, it's just easier to throw things at the Set and let the data structure do the work for you, then convert to a List on return. Otherwise, great explanation, good work!

[OctTEN_]

am so glad that he came back and run the code!!!

[praveen]

Do we have any other approach where we can reduce the time complexity?

[anvitabansal]

Sir how can it be solved using hashmap as in two sum problem where we can consider the target in two sum to be negative of nums[i] ?

[vasujhawar.]

How the hell, you made it look so easy.... man I am subscribing to your course.

[honeyjha]

This method doesn't gives the triplet [-1, -1, 2] because it skipped -1.

[hemaladani]

Took me a while to understand.
[i] != [i-1] because if same num[i] is found then results would also be the same. We want to avoid same results.
Same for
while(low<high && nums[low]==nums[low+1])
{
low++;
}
the result for that low is already calculated so skip it.

[shreyavhadadi]

What if the array contains only [-2, 1, 1] how does the code check for the duplicate?

[keremkeskin]

Thanks for solution. I have a question. Like this question, in some question, I have an error called Time Limit Exceeded. Actually code is true, but code can be crowded. What could you recommend for this issue?

[aylmao]

Can anyone explain the skip duplicate part?

[leezhenjian]

tough question for me, i couldn't get the solution for leetcode so i came here. helps alot, thanks man!

[vikrantbhati]

Will the solution work for array given 0, 0, 0, 0, 0, 0 and sum required is 0 ? I mean there should be one solution as 0, 0, 0 right ?

[ubaidullahaamir]

using dictionary we do not need to check for all the edge cases.

def threeSum(self, nums):

collection={}
nums = sorted(nums)
for index in range(len(nums)-2):
low=index + 1
high = len(nums)-1
target = 0 - nums[index]
while low < high:
if nums[low] + nums[high] == target:
temp = (nums[index], nums[low], nums[high])
if temp not in collection:
collection[temp] = list(temp)
low+=1
high-=1
elif nums[low] + nums[high] > target:
high -= 1
else:
low += 1
return collection.values()

[akshayrana]

Sorting: O(nlogn)
Two loops: O(n^2)
Duplicate check: O(n^2)
Total: O(n^2) + O(nlogn)

[TheCoolest]

I get a random runtime error at a test case during submission. "[-7, -4, -6, 6, 4, -6, -9, -10, -7, 5, 3, -1, -5, 8, -1, -2, -8, -1, 5, -3, -5, 4, 2, -5, -4, 4, 7]" is the last input. "Heap buffer overflow". Not sure where I'm going out of bounds in this case, just getting the registers in the error message.
Edit: Followed the call stack plugging it into visual studio, found the problem. Ran out of room for my answer vector. Updated the program to resize more appropriately. :) Unfortunately run time doesn't seem great. Not sure if the vector resizing is slowing it down.

[yadneshkhode]

sir thank you so much for people like me who can't afford courses you are great help sir did you upload all the problems you have ever solved on youtube or there are some which you haven't uploaded here

[GuruBala]

Your simple explanation just made it easy... but its not! You're awesome! <3