Is there really an O(n^2logn) solution?


  • 2
    E

    I've seen so many solutions which claim to have O(n^2logn) time complexity. However all of them have three-layer loop, which obviously not O(n^2logn). None of the authors have actually proved the time complexity of their solutions. I was hoping someone could give me a solution of time complexity O(n^2logn) and prove it.

    Thanks!


  • 0
    J

    My java solution is adopted from a c++ version from xinyu5. Thanks xinyu5.

    I believe the typical complexity is N^2, the worst case is N^3, as hashmap has typical complexity of O(1) for insert and get.

    The idea is during two level iteration i and j through num, we build the the hashmap to save all the possible pair combination into the hash map. So in the main iterator, we can check if the remain value is available in the map. If so, we will get the result.

    public class Solution {
    	public static class Pair {
    		int left;
    		int right;
    		Pair(int _left, int _right) {
    			left = _left;
    			right = _right;
    		}
    	}
    	public static List<List<Integer>> fourSum(int[] num, int target) {
    		Arrays.sort(num);
    		List<List<Integer>> result = new ArrayList<List<Integer>>();
    		Map<Integer, List<Pair>> map = new HashMap<>(); 
    		
    		for(int i=0; i<num.length - 1; i++) {
    			for(int j=i+1; j<num.length; j++) {
    				int remain = target - num[j] - num[i];
    				List<Pair> pairs = map.get(remain);
    				if(map.get(remain) != null)
    					for(Pair pair : pairs) {
    						List<Integer> list  = Arrays.asList(num[pair.left], num[pair.right], num[i], num[j]);
    						if(!result.contains(list))
    							result.add(list);
    					}
    			}
    			
    			for(int k=0; k<i; k++) {			
    				int sum = num[k] + num[i];
    				List<Pair> pairs = map.get(sum);
    				if(pairs == null) {
    					pairs = new ArrayList<>();
    					map.put(sum, pairs);
    				}
    				pairs.add(new Pair(k, i));
    			}
    		}
    		
    		return result;
    	}
    }

  • 0
    E

    I've seen his solution before. N^2 complexity should be the best and you're right about the worst time complexity. Therefore this solution has the time complexity of O(N^3). Note that the reason why it is O(N^3) has nothing to do with the internal structure of hash map. It's simply because of the existence of the most inner loop(A sum can correspond to multiple pairs). However what I'm really looking for is a solution of O(N^2LogN) time and the proof of the time complexity. And honestly, I don't believe it actually exists. Even if it does, complicated proof is required and it is not a trivial problem at all as many people think.


  • 9
    W

    Well, try to count the number of ways to have 4 numbers from [-n, -n+1, ...., n-1, n] with a sum of 0.
    The output size is at least c*n^3.
    So O(n^2logn) is definitely not possible.


  • -1
    V

    Approach 1:

    Let the input array be A[].

    1. Create an auxiliary array aux[] and store sum of all possible pairs in aux[]. The size of aux[] should be
      n(n-1)/2* where n is the size of A[]. Time complexity is O(n^2)

    2. Sort the auxiliary array aux[]. Time complexity is O(n^2logn) for sorting the array of size n^2

    3. Now the problem reduces to find two elements in aux[] with sum equal to X.

    The worst case time complexity of the algorithm is O(n^2logn) due to sorting operation of the auxiliary array.

    Approach 2:

    Here is another approach given by zhaohaoshu

    1. A TreeMap<Integer, List> to store pairs of numbers that can be used to get the number.

    2. Then iterate the map. When two lists of pairs that can get the target are found, cross join the pairs

    Map has N^2 keys. The n^2log(n) part is for doing insertion into the tree map. The time complexity to build the map is considered, as it is the deciding factor to consider the running time asymptotically which is O(n^2logn).

    NOTE: Above optimizations from O(n^3) time complexity are possible at the cost of auxiliary space of O(n^2) allocated for map.

    import java.util.TreeMap;
    
    public class Solution {
        class Pair {
            int a;
            int ai;
            int b;
            int bi;
    
            public Pair(int a, int ai, int b, int bi){
                this.a = a;
                this.ai = ai;
                this.b = b;
                this.bi = bi;
            }
    
            boolean same(Pair p){
                return p != null && p.a == a && p.b == b;
            }
        }
    
        public List<List<Integer>> fourSum(int[] num, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if(num.length < 4){
                return res;
            }
            Arrays.sort(num);
            TreeMap<Integer, List<Pair>> map = new TreeMap<>();
            for(int i = 0; i < num.length; i++){
                for(int j = i + 1; j < num.length; j++){
                    Pair pair = new Pair(num[i], i, num[j], j);
                    int sum = num[i] + num[j];
                    List<Pair> list;
                    if(map.containsKey(sum)){
                        list = map.get(sum);
                    }
                    else{
                        list = new ArrayList<>();
                        map.put(sum, list);
                    }
                    list.add(pair);
                }
            }
            Integer first = map.firstKey();
            Integer last = map.lastKey();
            while(first != null && last != null && first <= last){
                if(first + last > target){
                    last = map.lowerKey(last);
                }
                else if(first + last < target){
                    first = map.higherKey(first);
                }
                else if(first == last){
                    List<Pair> list = map.get(first);
                    for(int i = 0; i < list.size(); i++){
                        Pair a = list.get(i);
                        if(a.a == a.b){
                            for(int j = i + 1; j < list.size(); j++){
                                Pair b = list.get(j);
                                if(b.a == b.b){
                                    if(a.bi < b.ai){
                                        res.add(Arrays.asList(new Integer[]{a.a, a.b, b.a, b.b}));
                                        break;
                                    }
                                }
                                else{
                                    break;
                                }
                            }
                            break;
                        }
                    }
                    last = map.lowerKey(last);
                    first = map.higherKey(first);
                }
                else{
                    Pair lastA = null;
                    for(Pair a : map.get(first)){
                        if(a.same(lastA)){
                            continue;
                        }
                        lastA = a;
                        Pair lastB = null;
                        for(Pair b: map.get(last)){
                            if(a.bi < b.ai){
                                if(b.same(lastB)){
                                    continue;
                                }
                                lastB = b;
                                res.add(Arrays.asList(new Integer[]{a.a, a.b, b.a, b.b}));
                            }
                        }
                    }
                    last = map.lowerKey(last);
                    first = map.higherKey(first);
                }
            }
            return res;
        }
    }
    

  • 0
    A

    For Approach 1, step 3 is not exactly the same as to find two elements in aux[] with sum equal to X. Because we need a O(n) method for step 3 and we have duplicate elements. How to find out all 4 elements in nondecreasing order and no duplicate is not obvious. Can you post a code using approach 1?


  • 0
    E

    I doubt the correctness of approach 1 with similar reason as asafeather. Consider A[] = {1, 2, 3, 5}. The sums of all possible pairs are: 3(1, 2), 4(1, 3), 5(2, 3), 6(1, 5), 7(2, 5), 8(3, 5). If the target is 12, your approach will select 5(2, 3) and 7(2, 5), which is clearly not correct.


  • 0
    V

    In the step 3, the two elements obtained must not be in the pair, need to add that condition in the loop while finding two numbers in step 3


  • 0
    R

    Your above solution is giving TLE


  • 0
    E

    This proof is quite convincing. But since lots of people have given O(n^2logn) solutions, anyone wants to explain a bit about these solutions?


  • 0
    P

    I don't think your solutions are O(n^2logn). In solution 1, would you explain why sorting the auxiliary array aux[] is necessary? In solution 2, why using treemap instead of hashtable makes any difference?


  • 0
    T

    I can't directly see the correctness of this proof. Can you elaborate? And I believe the proof given by @vivek.bits is correct.


  • 0
    W

    One way to construct a size c*n^3 subset is,

    for each s from n/2 to 3n/2,  // n numbers
    
       for each pair of positive number with a sum s, // at least a*n pairs for some constant a
    
          for each pair of negative numbers with a sum -s // also a*n pairs
    
             the two pairs sum up to zero

  • 0
    C

    Hi eaglesky1990, have a see to my O(n*n) + O(scale of results) solution, welcome to challenge it!

    https://oj.leetcode.com/discuss/24581/there-maybe-isnt-a-n-2lgn-or-better-time-complexity-solution?show=25932#a25932


  • 0
    X

    The first approach is not n^2log(n) since in aux[] built in step 1, each sum or some of them would probably has O(n) pairs. To loop through them, O(n^3) in worst case.


  • 0
    L

    Think it this way:
    For the sequence -4, -3, -2, -1, 0, 1, 2, 3, 4, when choosing (-4, 4) as the initial pair, you have (-3, 3), (-2, 2), (-1, 1)'s help to total to zero, which is O(n). So does it for the initla pair (-3, 3), (-2, 2) or (-1, 1). So such combinations total to O(n^2).
    Yet we have more combos, like (-4, -1, 2, 3), and this means the complexity is definitely over O(n^2). Since we are doing combinations here, it cannot be O(n^2logn) and thus must be O(n^3).


  • 0
    Y

    Although I'm not sure about if there exists a n^2log n solution, the prove is not right logically. Yes, choosing 4 out of n has n^3 possibilities. However, keep in mind we have an extra constraint condition: sum to a target.


Log in to reply
 

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