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


  • 12
    F

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


  • 0
    S

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


  • 94
    L

    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)


  • 1

    @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?


  • 0
    G

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


  • 0

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


  • 0
    Z

    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)

  • 0

    @zion is that possible to share your code?


  • 0
    Z

    @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<>();
    
        // Start with the ends of the diagonal of the cube
        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) {
          finalSols.add(sol.toList());
        }
        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) {
          updateSol(ma, mb, mc, nums, sols);
        }
    
        // 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) {
              updateSol(a, b, c, nums, sols);
            }
          }
        }
      }
    
      private static void updateSol(int a, int b, int c, int[] nums, Set<Tuple3> sols) {
        Set<Integer> indices = new HashSet<>();
        indices.add(a);
        indices.add(b);
        indices.add(c);
        if (indices.size() == 3) {
          if (nums[a] + nums[b] + nums[c] == 0) {
            sols.add(new Tuple3(nums[a], nums[b], nums[c]));
          }
        }
      }
    
      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);
      }
    }
    

  • 2

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


Log in to reply
 

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