Question

Find pythagorean triplet in an unsorted array in java ?

int arr[] = {3, 1, 4, 6, 5};

Output:- 

[3, 4, 5]

Pythagorean: true

Answer 1

As we know that in simple math about the pythagorean as look like:- a² + b² = c^2.

A very simple solution to find pythagorean triplet. Run three loops and pick three array elements and check if current three elements form a Pythagorean Triplet. If found the print otherwise print not found.

This solution will take O(n^3) time complexity.

public static void main(String[] args) {
        int arr[] = {3, 1, 4, 6, 5};
        boolean isPythagorean = isPythagoreanTriplet(arr);
        System.out.println("Pythagorean: " + isPythagorean);
    }

//Time Complexity:- O(n^3).
    private static boolean isPythagoreanTriplet(int[] arr) {
        for(int i=0;i<arr.length; i++) {
            for(int j=i+1; j<arr.length; j++) {
                for(int k=j+1; k<arr.length; k++) {
                    if(((arr[i]*arr[i])+(arr[j]*arr[j]))==(arr[k]*arr[k])) {
                        System.out.println("["+arr[i]+", "+arr[j]+", "+arr[k]+"]");
                        return true;
                    }
                }
            }
        }
        return false;
    }

Output:-

[3, 4, 5]
Pythagorean: true

Answer 2

To find pythagorean triplet in unsorted array. See the solution is better way with O(n^2) time complexity using sorting. 

public static void main(String[] args) {

int arr[] = {3, 1, 4, 6, 5};

isPythagorean = isPythagoreanTripletUsingSorting(arr);

System.out.println("Pythagorean: " + isPythagorean);

}

//Time complexity:- O(n^2)

private static boolean isPythagoreanTripletUsingSorting(int[] arr) {

// Square array elements 

        for (int i = 0; i < arr.length; i++) 

            arr[i] = arr[i] * arr[i]; 

        // Sort array elements 

        Arrays.sort(arr); 

        // Now fix one element one by one and find the other two 

        // elements 

        for (int i = arr.length - 1; i >= 2; i--) { 

            // To find the other two elements, start two index 

            // variables from two corners of the array and move 

            // them toward each other 

            int start = 0; // index of the first element in arr[0..i-1] 

            int end = i - 1; // index of the last element in arr[0..i-1] 

            while (start < end) { 

                // A triplet found 

                if (arr[start] + arr[end] == arr[i]) {

                System.out.println("["+Math.sqrt(arr[start])+", "+Math.sqrt(arr[end])+", "+Math.sqrt(arr[i])+"]");

                    return true; 

                }

                // Else either move 'l' or 'r' 

                if (arr[start] + arr[end] < arr[i]) 

                    start++; 

                else

                    end--; 

            } 

        }

return false;

}