class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        return findTriplets(nums, 0);
    }
    
    public static List<List<Integer>> findTriplets(int[] nums, int requiredSum) {
        Set<List<Integer>> rs = new HashSet<>();
        getSortedArray(nums, 0, nums.length - 1);
        
       for(int i = 0; i < nums.length - 1; i++){
			for(int j = i + 1; j < nums.length; j++){
				int pairSum = nums[i] + nums[j];
				int elementToBeFound = requiredSum - pairSum;
				boolean isFound = binarySearch(nums, elementToBeFound, j + 1 , nums.length - 1);
				if(isFound){
					rs.add(Arrays.asList(nums[i], nums[j], elementToBeFound));
				}
			}
       }

        return new ArrayList<>(rs);
    }


    public static boolean binarySearch(int[] nums, int elementToBeFound, int start, int end){
    	int low = start;
    	int high = end;
    	while(low <= high){
    		int mid = low + (high - low) / 2;
    		if(nums[mid] == elementToBeFound) return true;

    		if(nums[mid] < elementToBeFound){
    			low = mid + 1;
    		}else if(nums[mid] > elementToBeFound){
    			high = mid - 1;
    		}
    	}

    	return false;
    }

    public static void getSortedArray(int[] nums, int low, int high){
    	if(low < high){
    		int pivot = partition(nums, low, high);
    		getSortedArray(nums, low, pivot - 1);
    		getSortedArray(nums, pivot + 1, high);
    	}
    }

    public static int partition(int[] nums, int low, int high){
    	int pivot = nums[high];
    	int i = low;

    	for(int j = low; j < high; j++){
    		if(pivot >= nums[j]){
    			swap(nums, i, j);
    			++i;
    		}
    	}

    	swap(nums, i, high);
    	return i;
    }

    public static void swap(int[] nums, int i, int j){
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }
}