14. Next Permutation

14. Next Permutation

Problem link :- click here

package programs;

import java.util.*;

public class Array__14
{
	
	static void nextPermutation(int[] arr)
	{
		int key, i;
		if(arr.length <= 1)
			return;
		for(i=arr.length-2; i>=0; i--)              //step 1
		{
			if(arr[i] < arr[i+1])
				break;
		}
		key = i;
		if(i == -1)                                     //in question 2nd para
		{
			reverse(arr, 0, arr.length-1);
			//we can reverse the array
			//instead of sorting it
			return;
		}
		for(i=arr.length-1; i>key; i--)              //step 2
		{
			if(arr[i] > arr[key])
			{
				swap(arr, i, key);
				break;
			}
		}
		reverse(arr, key+1, arr.length-1);              //step 3
		
		return;
	}
	

	public static void main(String[] args)
	{
		int i, n;
		
		Scanner s = new Scanner(System.in);
		System.out .println("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array\n");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given array :");
		print_array(array, n);
		System.out.println("\n");
		
		nextPermutation(array);
		System.out.println("\nNext permutation is :");
		print_array(array, n);
	}

	static void reverse(int[] arr, int i, int j)
	{
		while(i<j)
		{
			swap(arr, i, j);
			i++;
			j--;
		}
	}
	
	static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	static void print_array(int[] arr, int n)
	{
		for(int i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	}
}

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