Given an array arr[] of size N which is a permutation from 1 to N, the task is to find the lexicographically smallest permutation that can be formed by reversing at most one subarray.
Examples:
Input : arr[] = {1, 3, 4, 2, 5}
Output : 1 2 4 3 5
Explanation: The subarray from index 1 to index 3 can be reversed to get the lexicographically smallest permutation.Input : arr[] = {4, 3, 1, 2}
Output: 1 3 4 2
Approach: The idea to solve the problem is based on the traversal of the array.
- In the given problem the lexicographically smallest permutation can be obtained by placing the least number at its correct place by one reversal by traversing from left and checking (i+1) is equal to arr[i]
- If it is not equal find the index of that i+1 in the array and reverse the subarray from ith index to the position (i+1).
Below is the implementation of the above approach.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the // Lexicographically smallest // Permutation by one subarray reversal void lexsmallest(vector<int>& arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array reverse(arr.begin() + first, arr.begin() + last + 1); for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } } // Driver Code int main() { // Initialize the array arr[] vector<int> arr = { 1, 3, 4, 2, 5 }; int N = arr.size(); // Function call lexsmallest(arr, N); return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG{ // Function to find the // Lexicographically smallest // Permutation by one subarray reversal static void lexsmallest(int []arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { System.out.print(arr[i]+ " "); } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr = reverse(arr,first,last); for (int i = 0; i < n; i++) { System.out.print(arr[i]+ " "); } } } static int[] reverse(int str[], int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } return str; } // Driver Code public static void main(String[] args) { // Initialize the array arr[] int []arr = { 1, 3, 4, 2, 5 }; int N = arr.length; // Function call lexsmallest(arr, N); } } // This code contributed by shikhasingrajput |
Python3
# Python code for the above approach # Function to find the # Lexicographically smallest # Permutation by one subarray reversal def lexsmallest(arr, n): # Initialize the variables # To store the first and last # Position of the subarray first = -1 flag = 0 find = -1 last = -1 # Traverse the array # And check if arr[i]!=i+1 for i in range(0, n): if (arr[i] != i + 1): flag = 1 # Mark the first position # Of the Subarray to be reversed first = i find = i + 1 break # If flag == 0, it is the # Smallest permutation, # So print the array if (flag == 0): for i in range(0, n): print(arr[i], end=" ") # Check where the minimum element is present else: for i in range(0, n): # It is the last position # Of the subarray to be # Reversed if (arr[i] == find): last = i break # Reverse the subarray # And print the array arr[first: last + 1] = arr[first: last + 1][::-1] print(*arr) # Driver Code # Initialize the array arr[] arr = [1, 3, 4, 2, 5] N = len(arr) # Function call lexsmallest(arr, N) # This code is contributed by Samim Hossain Mondal. |
C#
// C# code for the above approach using System; class GFG{ // Function to find the // Lexicographically smallest // Permutation by one subarray reversal static void lexsmallest(int []arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { Console.Write(arr[i]+ " "); } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr = reverse(arr,first,last); for (int i = 0; i < n; i++) { Console.Write(arr[i]+ " "); } } } static int[] reverse(int[] str, int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } return str; } // Driver Code static public void Main (){ // Initialize the array arr[] int [] arr = { 1, 3, 4, 2, 5 }; int N = arr.Length; // Function call lexsmallest(arr, N); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach // Function to find the // Lexicographically smallest // Permutation by one subarray reversal const lexsmallest = (arr, n) => { // Initialize the variables // To store the first and last // Position of the subarray let first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (let i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (let i = 0; i < n; i++) { document.write(`${arr[i]} `); } } // Check where the minimum element is present else { for (let i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr.splice(first, last, ...arr.slice(first, last + 1).reverse()); for (let i = 0; i < n; i++) { document.write(`${arr[i]} `); } } } // Driver Code // Initialize the array arr[] let arr = [1, 3, 4, 2, 5]; let N = arr.length; // Function call lexsmallest(arr, N); // This code is contributed by rakeshsahni </script> |
Output
1 2 4 3 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
