TLE on 4Sum using hashtable


  • 0
    K

    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!


  • 0
    S

    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.


  • 6
    X

    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());
        }
    };

  • 0
    S

    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).


  • 0
    J

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


  • 0
    W

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


  • 0
    X

    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.


Log in to reply
 

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