# Any solution which is better than O(n^2) exists?

• For example, nlog(n)? since we have sort the array, it seems like we might able to do better.

• Could you please update your post to explain your `O(N^2)` solution first, then ask for more elegant solution? Thanks.

• No, you can't. If you're interested, here is a paper that proves a lower bound of Ω(n^ceil(k/2)) for the k-SUM problem (deciding whether k numbers out of n sums to 0) where ceil is the ceiling function. Here k=3, so you cannot do better than Ω(n^2).

Fun fact, there exist better quantum algorithms. The quantum complexity of k-SUM is Θ(n^(k/(k+1)) which is sub-linear! How cool is that? (Here is the paper describing the algorithm, and here the proof of optimality)

• @loick those papers are deep.... thanks

I have a doubt though: if the bound is Ω(n^ceil(k/2)), then for 4sum problem, the theoretically best solution should be O(n^2), but I cannot see anyone can solve that in O(n^2) time. What is wrong here?

Any one?

• @chidong a lower bound of Ω(n^ceil(k/2)) for the k-SUM problem

• @gpf828 Yeah.. I understand the lower bound part. So it is theoretically possible to find a O(n^2) solution?

• I believe there is O(nlogn) solution.

The basic idea is this:

1. Sort the array
2. With N numbers you can generate N^3 3-tuples
3. If the array is sorted sum(0,1,2) <= sum(len/2-1,len/2,len/2+1) <= sum(len-3, len-2, len-1). Note that the index in the inequality may be out of bounds, but it is only to provide the idea.
4. You can now imagine a cubic search space. And if you considered the center of the cube and compared with the diagonal ends, it can be seen that the problem can be reduced to 7/8 in each step.
4.1 for eg: If sum of cube mid point is greater than target sum. it can be noted that the cube with diagonal (mid,mid,mid) -> (len-1, len-1, len-1) can be dropped from search space. Note that the value uniqueness constraint in the 3-tuple should be additionally maintained.
5. It is a modification of binary search but in a 3 dimensional space.
6. Analysis: sort -> nlogn, search = 3/(log(8/7,2)/log(2)) * log(N, 2). Which implies a nlogn + ~5 logn solution. O(nlogn)

• @zion is that possible to share your code?

• @chidong This implementation timed out (but solutions were correct until it timed out). I am possibly missing something. From what I am reading, I assume folks have gotten an accept with n^2. Hope this helps.

``````public Solution {
private static class Tuple3 implements Comparable<Tuple3> {
// Implements a simple Tuple of three elements and is comparable.
// Skipping implementation for brevity
}

// Time complexity: O(nlogn) (nlogn for sort and O(logn) for search)
public static List<List<Integer>> threeSum(int[] nums) {
// Sort the input
Arrays.sort(nums);
int len = nums.length;
Set<Tuple3> sols = new TreeSet<>();

Tuple3 start = new Tuple3(0, 1, 2);
Tuple3 end = new Tuple3(len-3, len-2, len-1);
threeSum(nums, start, end, sols);

// Transform to list for returning the expected structure
List<List<Integer>> finalSols = new ArrayList<>();
for (Tuple3 sol : sols) {
}
return finalSols;
}

private static void threeSum(int[] nums, Tuple3 start, Tuple3 end, Set<Tuple3> sols) {
// Termination (when start > end)
if (start.getA() > end.getA()
|| start.getB() > end.getB()
|| start.getC() > end.getC()) {
return;
}

// Centroid of the cube
Tuple3 mid = centroid(start, end);

// Another termination condition where the cube is a unit cube.
// Handle specially
if (start.equals(mid)) {
unitCube(start, end, nums, sols);
return;
}

int sa = start.getA(); int sb = start.getB(); int sc = start.getC();
int ma = mid.getA(); int mb = mid.getB(); int mc = mid.getC();
int ea = end.getA(); int eb = end.getB(); int ec = end.getC();

// Sum of centroid
int sum = nums[ma] + nums[mb] + nums[mc];

// Found a solution
if (sum == 0) {
}

// If equal = 0 explore all 8 cubes. Else depending on whether sum is greater
// than or less than 0, we can skip one cube out of 8. The recursive calls take
// new diagonal end points of the sub cubes.
if (sum <= 0) {
threeSum(nums, new Tuple3(ma, mb, mc), new Tuple3(ea, eb, ec), sols);
}
if (sum >= 0) {
threeSum(nums, new Tuple3(sa, sb, sc), new Tuple3(ma-1, mb-1, mc-1), sols);
}
threeSum(nums, new Tuple3(ma, sb, sc), new Tuple3(ea, mb-1, mc-1), sols);
threeSum(nums, new Tuple3(sa, mb, sc), new Tuple3(ma-1, eb, mc-1), sols);
threeSum(nums, new Tuple3(ma, mb, sc), new Tuple3(ea, eb, mc-1), sols);
threeSum(nums, new Tuple3(ma, sb, mc), new Tuple3(ea, mb-1, ec), sols);
threeSum(nums, new Tuple3(sa, mb, mc), new Tuple3(ma-1, eb, ec), sols);
threeSum(nums, new Tuple3(sa, sb, mc), new Tuple3(ma-1, mb-1, ec), sols);
}

// Note that this function runs only for the case where distance(start, end) <= 1
private static void unitCube(Tuple3 start, Tuple3 end, int[] nums, Set<Tuple3> sols) {
for (int a = start.getA(); a <= end.getA(); ++a) {
for (int b = start.getB(); b <= end.getB(); ++b) {
for (int c = start.getC(); c <= end.getC(); ++c) {
}
}
}
}

private static void updateSol(int a, int b, int c, int[] nums, Set<Tuple3> sols) {
Set<Integer> indices = new HashSet<>();
if (indices.size() == 3) {
if (nums[a] + nums[b] + nums[c] == 0) {
}
}
}

private static Tuple3 centroid(Tuple3 a, Tuple3 b) {
int mida = (a.getA() + b.getA()) / 2;
int midb = (a.getB() + b.getB()) / 2;
int midc = (a.getC() + b.getC()) / 2;
return new Tuple3(mida, midb, midc);
}
}
``````

• Yes O(n^2/(log n/ log log n)^2/3) according to wiki (https://en.wikipedia.org/wiki/3SUM)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.