My Java solution [Quadratic bi-directional traversal + Trick for avoiding TLE!]


  • 6
    W

    Hello! I think most on here understand that the solution is based on the 2SUM problem. However, most of us (including myself) have encountered the dreadful TLE. So, the trick (as written in the comment below) is to avoid summing the same THREE elements again. That's it!

    Feel free to let me know should you have any queries OR if this solution can be improved upon!

    public List<List<Integer>> threeSum(int[] num) {
            List<List<Integer>> resultList = new ArrayList<List<Integer>>();
            if(num.length <= 2 || num == null)
                return resultList;
            Arrays.sort(num);
            HashSet<ArrayList<Integer>> tracker = new HashSet<ArrayList<Integer>>();
            int len = num.length;
            for(int i = 0; i < len-2; i++){
                //left
                int j = i+1;
                //right
                int k = len-1;
                while(j < k){
                    int sum = num[i] + num[j] + num[k];
                    if(sum == 0){
                        ArrayList<Integer> temp = new ArrayList<Integer>();
                        temp.add(num[i]);
                        temp.add(num[j]);
                        temp.add(num[k]);
                        if(tracker.add(temp)){
                            resultList.add(temp);
                        }
                        j++;
                        k--;
                        //HERE'S THE TRICK!
                        //We want to avoid summing up the same three elements again.
                        //So, we move the left and right pointers until they are different from previous result.
                        while(j < k && num[j] == num[j-1]){
                            j++;
                        }
                        while(j < k && num[k] == num[k+1]){
                            k--;
                        }
                    } 
                    else if(sum < 0)
                        j++;
                    else if(sum > 0)
                        k--;
                }
            }
            return resultList;
        }

  • 0

    most of us [...] have encountered the dreadful TLE

    How do you know? Are there statistics about that somewhere?


  • 0

    Also, if your "trick" avoids summing the same three again, then why do you still use your tracker set?


  • 9

    You can go further than that. Here's a Java translation of my previously posted C++ solution based on TigerHunter's solution:

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> triples = new ArrayList();
        Arrays.sort(nums);
        int i = 0, last = nums.length - 1;
        while (i < last) {
            int a = nums[i], j = i+1, k = last;
            while (j < k) {
                int b = nums[j], c = nums[k], sum = a+b+c;
                if (sum == 0) triples.add(Arrays.asList(a, b, c));
                if (sum <= 0) while (nums[j] == b && j < k) j++;
                if (sum >= 0) while (nums[k] == c && j < k) k--;
            }
            while (nums[i] == a && i < last) i++;
        }
        return triples;
    }

  • 0
    W

    Hi! It's just that I noticed that there was a significant amount of threads that questioned the TLE error. So, to avoid from diving too deep into the discussion forum, I thought I might help give a bit of clue as to why the TLE occurs (right from the front of the discussion page). It was not meant to insult anyone nor should this be the only solution to the problem. Everyone is entitled to ignore this post and go about with their own solution. Most likely, there are way better ones. Perhaps the word "trick" is a tiny bit exaggerated. More of a friendly tip, I suppose. :)

    This brings me to the solution that you have posted below. It's great! You don't even need to use a HashSet to keep track of the duplicates. So, I've learned that it is not really necessary to have a "tracker" implemented in this situation. :]


  • 0
    X
    for(int i = 0; i < len-2; i++){
         if(nums[i] > 0 || nums[len-1] < 0) 
        	break;
         if(i > 0 && nums[i] == nums[i-1]){
        	continue;
        }
      ....
        if(tracker.add(temp)){//couldn't need
            resultList.add(temp);
        }
    

  • 0
    M

    +1 for your last comment


  • 0
    H

    I think there is no need to continue the Outer loop while a > 0


  • 0

    Yes, you're right. Good point, thanks.


Log in to reply
 

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