LeetCode 15: 3Sum - Interview Prep Ep 20

Solution explained:
1. A direct intuition is the brute force way of tackling this problem: use a three layer nested for loop to iterate through the original input array, this way, we can find all possible triplets that add up to zero, then filter out the duplicate ones.
This is of course a "workable" solution, but is that acceptable/optimal?
It renders O(n^3) time complexity which is not ideal if not horrible. 🤪
2. We can do better than that for sure. Sorting is the rescue!
We could sort this array first, then use the famous two pointer technique to shrink the array to scanning from both ends.
Sorting: O(nlogn)
Iteration: O(n^2)
So total time complexity becomes: O(n^2), this is way better than O(n^3) when n is significant large. 😆

⭐ Support my channel and connect with me:

// TOOLS THAT I USE:

// MY FAVORITE BOOKS:

My ENTIRE Programming Equipment and Computer Science Bookshelf:

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures

[CengizAkarsu]

The video's sound very bad. Sometimes you hit or just touch your microphone. But thanks for your effort and clear explanation.

[laibamustafa]

if you have the sorted array [-4, -1, -1, 0, 1, 2] and you check for duplicated by continuing when nums[i - 1] == nums[i] -- then won't you in this case be skipping over the pair [-1, 0]?

[exceltokenizer]

Hi! if we can use extra space then shoudlnt we just insert all the elements into a set and then we can avoid the duplicate checks?

[sysybaba]

I did not really understand what your first for loop is doing? why even check for nums[i-1] if it does not even exist? I am missing something here?!

[BrajeshKumar-ezzs]

This solution does not work for [0, 0, 0]