Check if Pythagorean Triplet is present in an Array

You will be given an array of integers, you have to write a function which will return true if there is a triplet (a, b, c) that satisfies a^2+ b^2 = c^2 otherwise false.

We will solve the problem with the naive approach first then we will optimize our solution.

public class PythagoreanTripletInArray {
	//Naive solution in N^3
	
	private static Boolean IsPythagoreanTriplet(double d, 
			double e, double f) {
		if(d == (e+f))
			return true;
		else if(e == (d+f))
			return true;
		else if(f == (d+e))
			return true;
		
		return false;
	}
	public static void main(String[] args) {
		long startTime = System.nanoTime();
		
		int[] arr = new int[] {3, 1, 4, 6, 5};
		Boolean isPresent = false;
		for(int i=0;i<arr.length-2;i++) {
			for(int j=i+1;j<arr.length-1;j++) {
				for(int k=j+1;k<arr.length;k++) {
					if(IsPythagoreanTriplet( 
							Math.pow(arr[i],2),
							Math.pow(arr[j],2),
							Math.pow(arr[k],2))) {
						isPresent = true;
						break;
					}
				}
				if(isPresent)
					break;
			}
			if(isPresent)
				break;
		}
		
		System.out.println(isPresent);
		long endTime = System.nanoTime();
		long totalTime = endTime - startTime;
		System.out.println("Total Time (nanoseconds) : " + (totalTime));
	}
}

The time complexity of the above solution is O(N^3).

Output :

true
Total Time (nanoseconds) : 421758

Now we will optimize the solution for time complexity O(N^2).

import java.util.Arrays;

public class PythagoreanTripletInArray {
	//Optimized solution in N^2
	
	
	public static void main(String[] args) {
		long startTime = System.nanoTime();
		
		int[] arr = new int[] {3, 1, 4, 6, 5};
		Boolean isPresent = false;
		
		//sort the array
		Arrays.sort(arr);
		
		//find squares of each element in array
		for(int i=0;i<arr.length;i++) {
			arr[i]=(int) Math.pow(arr[i], 2);
		}
		
		
		// will pick last element and will compare for other two
		
		for(int i=arr.length-1;i>=0;i--) {
			int j=0;
			int k=i-1;
			while(j<k) {
				if(arr[i]==(arr[j]+arr[k])) {
					isPresent = true;
					break;
				}
				else if(arr[i]>(arr[j]+arr[k])) {
					j++;
				}
				else {
					k--;
				}
			}
			
			if(isPresent)
				break;
		}
		
		System.out.println(isPresent);
		long endTime = System.nanoTime();
		long totalTime = endTime - startTime;
		System.out.println("Total Time (nanoseconds) : " + (totalTime));
	}
}

true
Total Time (nanoseconds) : 798584

You will see the considerable time difference between these two approaches when the input size is very large.