# TLE on 4Sum using hashtable

• Hi,

I have used hash table(unordered_multimap) to store 2-number sum and their indices, and get 4 numbers when the sum of two 2-number sums is equal to target value. Checked the indices to keep 4 numbers are distinctive which means one number which has a certain index can not be used twice. Sorted 4 numbers and pushed to set to make the quadruplet unique. However, it got TLE.

I have 2 questions.

1. Does this method using hash table have quadratic performance? Is this a correct way?
2. Can you give an algorithm that has better performance and get accepted?

Thanks a lot!

• I would say your solution looks like a good solution, the time complexity seems O(N^2 * logN), assume the find function in unordered_multimap is O(log N).

Would you mind update your question with your code, and confirm the exact time complexity? Just a thought, maybe the problem is in implementation.

• Here is my solution (rather neat) using hash table with a time complexity of O(n^2 log n) (ignoring time for gathering answers), hope it will be helpful to you.

``````class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
sort(num.begin(), num.end());
unordered_map<int, set<pair<int, int>>> hash;
set<vector<int>> ans;
int n = num.size();
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
int a = num[i] + num[j];
if (hash.count(target - a)) {
for (auto &p: hash[target - a]) {
vector<int> b = {p.first, p.second, num[i], num[j]};
ans.insert(b);
}
}
}
for (int j = 0; j < i; j ++) {
int a = num[j], b = num[i];
hash[a + b].insert(make_pair(a, b));
}
}
return vector<vector<int>>(ans.begin(), ans.end());
}
};``````

• Your solution is pretty nice. I was just wondering the time complexity. Is it O(n^2 log n)? I think the complexity depends on how log has[target - a] could be. The best case (no duplicate of elements for the sum) would be O(n^2); the worst case I could think of would be something like: (e.g., [1, 6, 2, 5, 3, 4, 1, 7, 2, 6, 3, 5], and sum target is 15), and then the complexity would be O(n^3).

• looks like your solution is even better than N^2 Log (N), As hash table access usually take O(1).

• Neat!
But looks like this is an O(n^3) algorithm, as the inner loop can be linear.

• nice algorithm, but runs slowly. the actual runtime is same as the code written in java. this is much slower than the 3sum algrithm plus extra loop. I think this is caused by memory allocation and copy.

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