This should be n^2 Log(n), but performance is even worse


  • 0
    A

    I started with a O(n^3) approach, which passed. Then I thought the following would be faster, as it runs O(n^2 Log(n)), but I got TLE.

    The idea is to first find all pairs of 2 integers and calculate their sum, save to a map where key is sum and value is a TreeMap; this TreeMap sorts pairs by starting index.

    Then, for each pair1, I search for pair2 such that the sum of 2 pairs equals target.

    1. Find sum2.
    2. Look up pairs with sum=sum2 from map.
    3. Keep only pairs after pair1.
    4. Combine pair1 and pair2 to get a solution.
    public List<List<Integer>> fourSum(int[] num, int target) {
    	// key is sum, value is a tree of pairs whose sum equals to that key.
    	// these pairs are sorted by starting index,
    	// this allows us to find pairs whose sum=X, and are after index Y.
        Map<Integer, TreeMap<Integer, List<Integer>>> sumPairsMap = 
            new HashMap<Integer, TreeMap<Integer, List<Integer>>>();
        // map of each pair and its sum
        Map<List<Integer>, Integer> pairSumMap = 
            new HashMap<List<Integer>, Integer>();
        
        Arrays.sort(num);
            
        for (int i = 0; i < num.length - 1; i++) {
            for (int j = i + 1; j < num.length; j++) {
                int sum = num[i] + num[j];
                List<Integer> pair = new ArrayList<Integer>(2);
                pair.add(i);
                pair.add(j);
                TreeMap<Integer, List<Integer>> pairs = sumPairsMap.get(sum);
                if (pairs == null) {
                    pairs = new TreeMap<Integer, List<Integer>>();
                    sumPairsMap.put(sum, pairs);
                }
                pairs.put(i, pair);
                pairSumMap.put(pair, sum);
            }
        }
        
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        for (Map.Entry<List<Integer>, Integer> entry : pairSumMap.entrySet()) {
            List<Integer> pair = entry.getKey();
            int end = pair.get(1);
            int sum1 = entry.getValue();
            int sum2 = target - sum1;
            TreeMap<Integer, List<Integer>> pairs = sumPairsMap.get(sum2);
            if (pairs == null)
                continue;
            for (List<Integer> subPair : pairs.tailMap(end + 1).values()) {
                List<Integer> result = new ArrayList<Integer>(4);
                result.add(num[pair.get(0)]);
                result.add(num[pair.get(1)]);
                result.add(num[subPair.get(0)]);
                result.add(num[subPair.get(1)]);
                set.add(result);
            }
        }
        
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        results.addAll(set);
        return results;
    }

  • 0
    F

    The worst situation should be O(n^4) I think,since in the last loop, the outer 'for' should be O(n2) and the inner 'for' also could be O(n2) because it's possible that O(n2) pairs sum to the same value


Log in to reply
 

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