Find a triplet that sum to a given value gives TLE in Java

Question

I am trying to solve this question https://practice.geeksforgeeks.org/problems/triplet-sum-in-array-1587115621/1# I have used a HashMap to store all the possible sums along with an array of indices whose sum I have stored. This is my code

  class Solution
 {

//Function to find if there exists a triplet in the array A[] which sums up to X. 
  
 public static boolean find3Numbers(int arr[], int n, int X){ `
  
 HashMap<Integer,ArrayList<Pair>> hm=new HashMap<>();

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(!hm.containsKey(arr[i]+arr[j])){hm.put(arr[i]+arr[j],new ArrayList<>());}
            Pair pair=new Pair(i,j);
            ArrayList<Pair> list=hm.get(arr[i]+arr[j]);
            list.add(pair);
            hm.put(arr[i]+arr[j],list);
        }
    }
    for(int i=0;i<n;i++){
        if(hm.containsKey(X-arr[i])){
            ArrayList<Pair> p=hm.get(X-arr[i]);
            for(int k=0;k<p.size();k++){
                if(p.get(k).ind1!=i && p.get(k).ind2!=i)return true;
            }
        }
    }
    return false;
}
public static class Pair{
    int ind1;
    int ind2;
    Pair(int i,int j){
        ind1=i;
        ind2=j;
    }
}
}

Please tell me why am I getting TLE?

Answer 1

From the description of the problem, time complexity should be O(n^2). But this part of your code is not O(n^2), in worst case it is O(n^3)

for(int i=0;i<n;i++){
    if(hm.containsKey(X-arr[i])){
        ArrayList<Pair> p=hm.get(X-arr[i]);
        for(int k=0;k<p.size();k++){
            if(p.get(k).ind1!=i && p.get(k).ind2!=i)return true;
        }
    }
}

Because ArrayList's size can be n^2. For example, [1,1,1,1,1]. List of pairs which sum is 2 is 10.

(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 = (n - 1) * n / 2 ≈ n^2

The possible solution:

public static boolean find3Numbers(int arr[], int n, int X){
    Arrays.sort(arr);
    for (int i = 1; i < n - 1; i++) { // from the second to penultimate
        int l = 0; // first index
        int r = n - 1; // last index
        while (l < i && r > i) {
            int sum = arr[l] + arr[r] + arr[i];
            if (sum == X)
                return true;
            if (X > sum)
                l++;
            else
                r--;
        }
    }
    return false;
}

• time complexity - O(n^2)
• space complexity - O(1)

This approach is also called "Two Pointer technique", it is widely used in algorithmic problems. If you are interested, you can find a lot of information on the internet.