27. Triplet sum in Array

27. Triplet sum in Array

Problem link :- click here

package programs;

import java.util.*;

public class Array__27
{

	static Boolean triplet(int arr[], int n, int sum)
	{
		quickSort(arr, 0, n-1);
		for(int i=0; i<n-2; i++)
		{
			int j = i+1;
			int k = n-1;
			while(j<k)
			{
				if(arr[i] + arr[j] + arr[k] == sum)
				{
					System.out.println("\n\nTriplet is : " + arr[i] + " " + arr[j] + " "  + arr[k] );
					return true;
				}
				else if(arr[i] + arr[j] + arr[k] < sum)
					j++;
				else
					k--;
			}
		}
		return false;
	}
	
	static void quickSort(int arr[], int start, int end)
	{
		int pos;
		if(start < end)
		{
			pos = partition(arr, start, end);
			quickSort(arr, start, pos-1);
			quickSort(arr, pos+1, end);
		}
	}
	
	static int partition(int arr[], int start, int end)
	{
		int pivot, i, j;
		pivot = arr[end];
		i = start-1;
		j = start;
		for(j=start; j<end; j++)
		{
			if(arr[j] < pivot)
			{
				i++;
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		i++;
		int temp = arr[end];
		arr[end] = arr[i];
		arr[i] = temp;
		
		return i;
	}
	
	public static void main(String[] args)
	{
		int n, i, sum;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.print("Enter the sum : ");
		sum = s.nextInt();
		
		System.out.println("Given Array : ");
		print_array(array);
		
		Boolean ans = triplet(array, n, sum);
		if(!ans)
			System.out.println("\n\nTriplet not found");
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time comlexity :- O(n²)
Space complexity :- O(1)