Why am I getting TLE for O(n^2) algorithm


  • 0
    H

    I thought it is a O(n^2) algorithm, but I kept getting TLE. Anyone knows why?

    public class Solution {
            public List<List<Integer>> threeSum(int[] num) {
                Arrays.sort(num);
                List<List<Integer>> list = new ArrayList<List<Integer>>();
                List<Integer> triplet = new ArrayList<Integer>();
                if (num.length < 3) return list;
                int low = 0;
                int high = 0;
                
                for (int i = 0; i < num.length - 2; i++) {
                    if (i >= 1 && num[i] == num[i-1]) continue;
                    low = i + 1;
                    high = num.length - 1;
                    while (high > low) {
                    if (num[low] + num[high] == -num[i]) {
                        triplet.add(num[i]);
                        triplet.add(num[low]);
                        triplet.add(num[high]);
                        list.add(triplet);
                        low++;
                        high--;
                    }
                    else if (num[low] + num[high] < -num[i]) {
                        low++;
                    }
                    else {
                        high--;
                    }
                    while (num[low] == num[low-1] && high > low) low++;
                    while (high+1 <= num.length-1 && num[high] == num[high+1] && high > low) high--;
                    }
                }
                return list;
                
            }
        }

  • 0
    W

    You keep adding items to the same triplet, should use triplet = new ArrayList<Integer>(); for each sum equal~


  • 0
    H

    Thanks! After I fixed the TLE problem, I also found another bug in my code too.


Log in to reply
 

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