TLE for O(n^2) solution


  • 6
    V

    In my solution, I calculate Si+Sj for every pair i, j from S and insert it into a hash map. This takes O(n^2). I then iterate over S and lookup -(Sk) for each k in the hash map. Lookup time for the hash map is O(1) on average.
    I am still getting a TLE for my submission. C++ has a good implementation of hash map(unordered_map), and there shouldn't be much collision for the input shown to me(~200 elements)

    class Solution {
    public:
    vector<vector<int> > threeSum(vector<int> &num) {
        unordered_map<int, pair<int, int> > m;
        vector<vector<int> > soln;
        for(int i =0;i < num.size();i++) {
            for(int j = i + 1;j < num.size();j++) {
                m.insert(make_pair(num[i] + num[j], make_pair(i, j)));
            }
        }
        
        for(int i =0;i < num.size();i++) {
            auto it = m.find(-num[i]);
            if(it != m.end()) {
                if(i != it->second.second && i != it->second.first) {
                    vector<int> v;
                    v.push_back(num[i]);
                    v.push_back(num[it->second.first]);
                    v.push_back(num[it->second.second]);
                    soln.push_back(v);
                }
            }
        }
        
        return soln;
        
    }
    

    };


  • 0
    C

    This code looks clean and highly readable. But how did you make sure that the order is right?


  • 0
    T

    I will sort the list first, then I will insert the solution into a hashset, then convert it to solution list.

    public class Solution {
        public List<List<Integer>> threeSum(int[] num) {
            List<List<Integer>> answer = new ArrayList<List<Integer>>();
            Set<List<Integer>> answerSet= new HashSet<List<Integer>>();
            sort(num);
            for (int i = 0; i < num.length; i++)
            {
                int j = i + 1;
                int k = num.length - 1;
                while (j < k)
                {
                    int target = -1 * num[i];
                    int sumOfTwo = num[j] + num[k];
                    if (sumOfTwo == target)
                    {
                        List<Integer> tripplets = new ArrayList<Integer>();
                        tripplets .add(num[i]);
                        tripplets .add(num[j]);
                        tripplets .add(num[k]);
                        answerSet.add(tripplets );
                        j++;
                        k--;
                    }
                    else if (sumOfTwo > target)
                    {
                        k--;
                    }
                    else
                    {
                        j++;
                    }
                }
    
            }
            
            for(List<Integer> solution : answerSet)
            {
                answer.add(solution);
            }
            return answer;        
        }
        
        public void sort(int[] num)
        {
            for(int i = 0; i < num.length;i++)
            {
                int min = num[i];
                for(int j = i + 1; j < num.length;j++)
                {
                    if(num[j] < min)
                    {
                        num[i] = num[j];
                        num[j] = min;
                        min = num[i];
                    }
                }
            }
        }
    }

  • 0
    Z

    I think I have similar situation with you. If you could sort the array first, then you can save a lot of time for duplication elements.


  • 0
    V

    I reviewed my solution and realized that it doesn't always give the correct solution. It may miss some combinations, and it may include some duplicates. eg it might generate (2,3,2) twice and miss 1,4,2 upon input {1,2,2,3,4} and sum 7


Log in to reply
 

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