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

• 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);
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);