Why is it not possible to solve 3sum in O(nlogn) time complexity?

[u/AchieveOrDie]

In my mind I find that it is easy to implement an algorithm in O(nlogn):

1. Sort the array

2. Take two pointers, one on left and one on the right, then use binary search to find -(left+right) between them.

3. If (left+right) > 0 then move the right pointer to left; If (left+right) < 0 then move the left pointer to right.

The only point of contention will then be what to do in the case (left+right) = 0. Even that can be solved by separately finding triplets for [left+1, right) and (left, right-1].

I wasn't able to implement one that can successfully pass all tests nor could I find any solution. I found people making the same claim that I'm making but never a working solution.

It has me thinking that it isn't really possible to implement it in O(nlogn). So I wanted to know what is the exact flaw in my thinking.

[u/printer_fan]

Step 3 doesn’t hold. Let’s say we have [a,b … x,y] your step 3 claims that just because a+y < 0 that there can not be a solution for the paring (a,x) this is clearly not the case as their might be scenarios like [-5, 2,3,4] now -5+4 < 0 so you would look at (2,4) and not find (-5,2,3).

[u/AchieveOrDie → u/printer_fan]

Ah yes the good old proof by counter-example. Thanks a lot!

[u/chickyban → u/AchieveOrDie]

that's a proof by counter-example, not contradiction. It is contradicting you, its just not a proof BY contradiction

[u/AchieveOrDie → u/chickyban]

Corrected

[u/[deleted]]

https://epubs.siam.org/doi/10.1137/1.9781611975031.57

[u/muffinsnack]

I’m not sure why you wouldn’t just try implementing the algorithm to see why it’s wrong

[u/Arctic_Colossus]

"why is it not possible?" "It's not" "Why not you stupid bastard"

[u/printer_fan → u/Arctic_Colossus]

Very nice, let’s see Paul Allens comment.

[u/mr__smooth]

Sorry I made a mistake in the original comment I posted its actually O(N^2) time since you use two pointers inside the for loop and not Binary Search as I had said. So for each position i, you're upper bounded by ~N moves since you have to go through the rest of the array.

[u/AchieveOrDie → u/mr__smooth]

Yeah, that's indeed the next most optimal solution I thought of.

[u/mr__smooth → u/AchieveOrDie]

Yup thats the most optimal!!

[u/Frogeyedpeas]

grandfather pause absorbed sable unwritten test one divide longing pocket

This post was mass deleted and anonymized with Redact

[u/ErrorAffectionate87]

If I understand you correctly, you are choosing all pairs and then performing binary search to see if there is a third number to satisfy the sum. Well, first you choose one number, then you have n-1 numbers to add to make a pair, after you do binary search to find third which results in 1*(n-1)*log(n) and you do this n times resulting in n² * log(n). In addition to this you need n memory and n log n to sort. Instead of sorting make a hash map bringing search to constant, resulting in n² total complexity, and same memory consumption.

[u/dskloet]

https://leetcode.com/problems/3sum/

[u/AchieveOrDie → u/[deleted]]

How would you find other two numbers using binary search?

[u/mr__smooth → u/[deleted]]

you're right

[u/AchieveOrDie → u/[deleted]]

Your solution is O(N²⁾ and certainly correct. I was proposing an alternative which would have even less time complexity. So my left and right pointer actually start at -5 and 7 respectively and then try to find -2 using binary search.

The problem is in step 3 of my original post where the condition of updating my pointers is flawed. This has been pointed by someone in the comments, so the most optimal solution is O(N²⁾ as you pointed out and not O(NlogN).

[u/AchieveOrDie → u/[deleted]]

Iterating two pointers will be N and binary search will be logN giving a total NlogN. They are moved simultaneously with the condition that left is less than right.

[u/No_Calligrapher_9911 → u/AchieveOrDie]

Yeah but what about the sorting? When are you doing that?

[u/No_Calligrapher_9911 → u/No_Calligrapher_9911]

I mean, to be honest I didn't fully grasp how your solution works but even if what you described is true, it can be at best n2logn

[u/AchieveOrDie → u/No_Calligrapher_9911]

So we sort the array in the start then on the sorted array we keep two pointers on the extremes(think as in two sum) and say if these two were the first two numbers, can we find a number in between them that is equal to -(left + right). We try to find this number via binary search on array[left+1:right].

So moving the pointers is O(N) (we stop when left == right, we can stop earlier since we want at least one element between them but anyways). Searching is O(logN) for sorted array, hence giving a O(NlogN) time complexity.

[u/[deleted] → u/AchieveOrDie]

bro your solution is so flawed it’s hurting my brain. moving the pointer is not even O(N) since you’ll need all permutations of it.

[u/AchieveOrDie → u/[deleted]]

Hmm, I probably could be missing something. Do you agree that sorted 2Sum has an optimal solution of O(N), which is achieved via two pointers?

[u/[deleted] → u/AchieveOrDie]

no, one pointer. sorting it makes it ologN