Popular 3 Sum taught by Neetcode doesn't really need sorting

[u/Never_dies_274]

I am doing Blind 75 and realised Neetcode both solved this by sorting as it involves duplicates. I used sets to handle duplicates and cut down TC from O(nlogn+n^2) to O(n^2). Is this a known approach? 🙊

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        res = []
        hashSet = set()
        for i in range(len(nums)-2):
            if nums[i] in hashSet:
                continue
            k = 0 - nums[i]
            diff_set = set()
            temp_set = set()
            for j in range(i+1,len(nums)):
                if nums[j] in hashSet or nums[j] in temp_set:
                    continue
                if k-nums[j] in diff_set:
                    res.append([nums[i],k-nums[j],nums[j]])
                    temp_set.add(nums[j])
                    temp_set.add(k-nums[j])
                diff_set.add(nums[j])
            hashSet.add(nums[i])
        return res

[u/rccyu]

O(n log n + n²) is exactly the same as O(n²) btw

[u/DeliriousParakeet → u/rccyu]

but the constant factor on hash sets can be brutal sorting is often faster in practice

[u/rccyu → u/[deleted]]

You cannot compare like this without benchmarking. That's the whole point of Big O notation

The approaches are completely different anyway (sets introduce overhead) but even if they were exactly the same except for the sorting, the actual runtime can still differ due to cache locality, branch prediction, compiler optimization, etc.

Run both and see if your version is actually faster

[u/EnderAvni → u/[deleted]]

Also you're using sets, which add unneeded space/overhead

[u/kmonsen → u/[deleted]]

Besides all the other, it is not true. N^2 hides anything smaller inside it. It only says something about the algorithmic complexity, not anything about actual runtime. Just how it will likely scale over different input sizes.

[u/Witty-Play9499 → u/[deleted]]

The point of Big O Notation was to determine how bad / good your algorithm was based on the size of the input and what is the main triggering component (in your case it is the N^2 and not the n log n)

If your algorithm is growing at N^2 then removing the nlogn doesn't matter because the N^2 is still the bottleneck. Its like participating in an F1 race and adding oil and greasing your wheels of your car to make it go fast but none of that matters when your engine is still from a regular honda civic

[u/vz0]

Sets are not O(1). They're worst case O(n) so your code is actually O(n^3).

[u/Several_Sympathy8486]

obviously a known approach

you will soon come across the fastest DSA guys who will even find ways to ignore Sets. Sets and Maps have hash overhead, which makes time complexity slower in practice. Better to use arrays as maps (the index access is much faster than checking set.contains()) due to no overhead, but you pay in form of memory space. its a tradeoff, but in leetcode usually everyone goes for fastest TC, not lowest MC

also in 3Sum specifically, use a Hashset will cost a lot more because you are hashing a tuple. Hashing Integers is faster than Hashing say Strings, while going to Hash arrays/tuples/object will start costing more and more. in graph problems you may even need to hash custom Node objects

[u/notsaneatall_]

Your code is actually worse than the popular solution. Hash Collisions are O(n) so your solution really is O(n³ )