31. Three way partitioning

31. Three way partitioning

Problem link :- click here

package programs;

import java.util.*;

public class Array__31
{

	static void threeWayPartition(int arr[], int low_value, int high_value)
	{
		int start, end, n, j;
		n = arr.length;
		start = -1;
		end = n;
		
		/*
		    same as partition in quick sort 
		    there  ->  pivot(only one)
		    here   ->  low_value, high_value(two)
		    
		    there  ->  we have to make it    two      parts
		    here   ->  we have to make it    three    parts
		 */
		
		/*
		    NOTE:-  BE CAREFUL ABOUT THE CONDITION
		        IF 
		    	   'j' exceeds the 'end' then it will swap the sorted array
		    	OR
 			   'j' should not enter the sorted part of array
		*/
		for(j=0; j<end; )
		{
			if(arr[j] < low_value)
			{
				start++;
				int temp = arr[j];
				arr[j] = arr[start];
				arr[start] = temp;
				j++;
			}
			else if(arr[j] > high_value)
			{
				end--;
				int temp = arr[j];
				arr[j] = arr[end];
				arr[end] = temp;
				/*
				    not incrementing 'j' 
				    because we don't know what is the value 
				    of the element in  'j' after swapping
				*/
			}
			else
				j++;
		}
		/*
		    we don't need other swap as there
		    because we are taking any element in array as pivot 
		    Here The value is already given
		*/
	}
	
	public static void main(String[] args)
	{
		int n, i, low_value, high_value;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size 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 low value of the range : ");
		low_value = s.nextInt();
		System.out.print("Enter the high value of the range : ");
		high_value = s.nextInt();
		
		System.out.println("Given Array : ");
		printArray(array);
		
		threeWayPartition(array, low_value, high_value);
		System.out.println("\n\nArray after modification : ");
		printArray(array);
	}
	
	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

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