content: package math;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  import java.util.Random;
  
  public class FindPythagoreanTriplets {
  
  
      /*
       * Given an integer array find all Pythagorean triplets (a^2 + b^2 = c^2).
       * Input: 4, 16, 1, 2, 3, 5, 6, 8, 25, 10
       *
       * the Pythagorean triplets are (3, 4, 5) and (6, 8, 10) as
       * 32 + 42 = 52 and 62 + 82 = 102
       *
       * Runtime Complexity:
       * Quadratic, O(n2)
       *
       * Memory Complexity:
       * Constant, O(1).
       *
       *
       * */
  
  
      protected static List<int[]> findPythagoreanTriplets(int[] arr) {
          int n = arr.length;
          List<int[]> triplets = new ArrayList<int[]>();
          Arrays.sort(arr);
  
          for (int i = 0; i < n; ++i) {
              if (arr[i] == 0) continue;
  
              int c2 = arr[i] * arr[i];
  
              int j = 0;
              int k = n - 1;
  
              while (j < k) {
                  if (j == i || arr[j] == 0) {
                      j += 1;
                      continue;
                  }
  
                  if (k == i || arr[k] == 0) {
                      k -= 1;
                      continue;
                  }
  
                  int a2 = arr[j] * arr[j];
                  int b2 = arr[k] * arr[k];
  
                  if (a2 + b2 == c2) {
                      triplets.add(
                              new int[]{arr[i], arr[j], arr[k]});
                      break;
                  } else if (a2 + b2 + (-c2) > 0) {
                      k -= 1;
                  } else {
                      j += 1;
                  }
              }
          }
          return triplets;
      }
  
  
      public static void main(String[] argv) {
  
          int[] l2 = {13, 4, 25, 6, 8, 110, 99, 32, 15, 18, 19};
          List<int[]> t2 = findPythagoreanTriplets(l2);
  
          System.out.println("***********");
          for (int[] a : t2) {
              for (int x : a) {
                  System.out.print(x + ", ");
              }
              System.out.println();
          }
      }
  }
  