Tuesday, December 23, 2014

Find pythagorean triplets

I am doing this because of this post on Stackoverflow. The question is if there is an O(n) method to do this. Some replies are about using the same approach of  3Sum in LeetCode. I tried both the backtracking way and the 3Sum approach. Based on the code, they are both close to O(n^2) complexity. I tested both, honestly, even the 3Sum can be slightly faster because we trimmed of some iterations, no tremendous improvement.


import java.util.*;


public class PythagoreanTriple {
        //3Sum approach
 public ArrayList> findPythagorean(int[] nums) {
  ArrayList> rst = new ArrayList>();
  if (nums == null || nums.length == 0) {
   return rst;
  }
  Arrays.sort(nums);
  int[] square = new int[nums.length];
  for (int i = 0; i < nums.length; i++) {
   square[i] = nums[i] * nums[i]; 
  }
  for (int i = 0; i < nums.length - 2; i++) {
   if (i != 0 && nums[i] == nums[i - 1])
    continue;
   int left = i + 1;
   int right = nums.length - 1;
   while (left < right) {
    int sum = square[i] + square[left] - square[right];
    if (sum == 0) {
     ArrayList list = new ArrayList();
     list.add(nums[i]);
     list.add(nums[left]);
     list.add(nums[right]);
     rst.add(list);
     left++;
     right--;
     while (left < right && square[left] == square[left - 1]) {
      left++;
     }
     while (right > left && square[right] == square[right + 1]) {
      right--;
     }
    }
    else if (sum < 0) {
     right--;
    }
    else
     break;
   }
  }
  return rst;
 }
        //backtracking
 public ArrayList> findPythagorean2(int[] nums)
 {
  ArrayList> rst = new ArrayList>();
  if (nums == null || nums.length == 0)
   return rst;
  ArrayList tri = new ArrayList();
  Arrays.sort(nums);
  findTriangle(rst, tri, nums, 0);
  return rst;
 }
 private void findTriangle(ArrayList> rst, ArrayList tri, int[] nums, int start) {
  if (tri.size() == 3) {
   if (tri.get(0) * tri.get(0) + tri.get(1) * tri.get(1) == tri.get(2) * tri.get(2)) {
    rst.add(new ArrayList (tri));
   }
   return;
  }
  for (int i = start; i < nums.length; i++) {
   if (i != start && nums[i] == nums[i - 1])
    continue;
   tri.add(nums[i]);
   findTriangle(rst, tri, nums, i + 1);
   tri.remove(tri.size() - 1);
  }
 }
}

No comments:

Post a Comment