2

I was thinking of various approaches for finding the triplet sum and I came across this finding a triplet having a given sum. So I thought of giving it a try.

My algorithm:
1) Sort the numbers //O(nlogn)
2) Initialize low=0 and high=size-1
3) loop till low<high
   a) if sum-arr[high]-arr[low]< 0 , then decrement high
   b) if third number is not in range of (low,high) then break the loop
   c) else search for third number using binary search

But I am not getting correct output. I don't know where my logic is wrong because its pretty much simple binary search. Below is what I have implemented. Please let me know my mistake 

static boolean isTriplet(int a[], int size, int sum)
    {
       Arrays.sort(a);  //sort the numbers

        int low = 0;
        int high = size-1;
        while(low<high)
        {

            int third = sum - a[high] - a[low];
            if(third<0)
                high--;
            else if(!(sum - a[high] - a[low]>a[low] && sum - a[high] - a[low]< a[high]))  //if the number is not within the range then no need to find the index
                break;
            else
            {
                int index = binarySearch(a,low+1,high-1,third);
                if(index != -1)
                {
                    System.out.println(a[low]+" "+a[index]+" "+a[high]);
                    return true;
                }
                else
                low++;                  

            }

        }
        return false;
    }

I tried it with input {1,2,3,4,5,6} and sum=6 but it returns false and when input was {3,4,8,1,2,7,5} and sum=20 it returned true

Community
  • 1
  • 1
Ankita
  • 37
  • 8

1 Answers1

1

I partially understood your idea, not completely. It seems like you are trying to solve the problem in O(n log(n)) time complexity and I am not confident that it is possible. I am not sure how you decide to do this:

           else
            low++;

I doubt that in some cases maybe you should do 

high--

there. Also I am not sure about this piece of code:

if(third<0)
   high--;

What if third > 0, but it's less than low?

I read the other question and it proposes a O(n^2 logn) solution, so I provided here such a solution (in Java).

The idea is: iterate with 2 nested for loops (i, j) through all pairs of elements and look up for the third element which would complement the triplet in the rest of the array (that lookup is done using binary search - the while loop.

public class TripletSum {
    static boolean solve(int[] a, int k) {
        Arrays.sort(a);
        int n = a.length;

        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                int low = j + 1, high = n - 1;

                while(low <= high) {
                    int middle = (low + high) / 2;
                    int sum = a[middle] + a[i] + a[j];
                    if(sum == k) {
                        return true;
                    }
                    if(sum > k) {
                        high = middle - 1;
                    }
                    if(sum < k) {
                        low = middle + 1;
                    }
                }

            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6};

        System.out.println(solve(a, 20));
    } 
}

EDIT: I did some research and couldn't find a O(N logN) solution for this problem. Turns out this problem is popular as 3SUM. You can see on the Wiki page there is a Quadratic solution which beats the O(N^2 logN).

giliev
  • 2,938
  • 4
  • 27
  • 47
  • Thanks for the O(N^2 logn) solution. Yes,I was trying to solve it in O(nlogn) .Regarding the edge cases, `low++` is when the binarySearch function is not able to find the index of third, so the function will return -1 and I increment low. But now I also feel something wrong here because when I check `else if(!(sum - a[high] - a[low]>a[low] && sum - a[high] - a[low]< a[high]))` it will break the loop and I am not incrementing or decrementing anything. But this condition will take care of the case you mentioned when `third>0` but less than low. Any suggestions here? – Ankita Apr 01 '17 at 03:45
  • @Ankita I edited my answer. I think the Quadratic solution has similar approach as yours, but there isn't any binary search. – giliev Apr 01 '17 at 10:04