package algoexpert.medium;
import java.util.ArrayList;
import java.util.Arrays;

/*
PROBLEM:
Find all triplets that sum upto target
Return in ascending order

LOGIC:
a + b + c = k
a + b = k - c [Two Sum -> O(n)]

Solutions:
1. Sort and Two pointer -> t: O(n^2) | space: O(n) -> solution array
2. Brute Force -> t: O(n^3) | s : O(n)
3. Binary Search (for every two) -> t : O(n^2 log n) | s : O(n)
4. Search in set (for every two) -> t : O(n^2) | s : O(n + m) -> set
*/

public class ThreeSum
{
    public static <T> void printArr(T [] array)
    {
        for (T x : array) { System.out.print(x + " "); }
        System.out.println();
    }

    public static void test()
    {
        int [] test = {12,3,1,2,-6,5,-8,6};
        int target = 0;
        for (Integer [] triplet : threeNumberSum(test, target) ) { printArr(triplet);}
    }

    public static ArrayList<Integer[]> threeNumberSum(int[] array, int targetSum)
    {
        Arrays.sort(array);
        ArrayList<Integer[]> solution = new ArrayList<Integer[]> ();

        for (int i = 0; i < array.length - 2; ++i)
        {
            int first = i + 1;
            int last = array.length - 1;

            int findSum = targetSum - array[i];
            while(first < last)
            {
                int currentSum = array[first] + array[last];
                if (currentSum == findSum)
                {
                    // add to solution
                    Integer [] triplet = new Integer[] { array[i], array[first], array[last]};
                    solution.add(triplet);
                    first += 1;
                    last -= 1;
                }
                else if (currentSum < findSum)
                {
                    first += 1;
                }
                else
                { last -= 1 ; }
            }
        }
        return solution;
    }
}