Given an array A[] of length N, the task is to find lexicographically smallest array by swapping adjacent elements for each index atmost once. Thus, for any index:
, at most one swap between A[K] and A[K+1] is allowed.
Example:
Input: A[] = { 3, 2, 1, 4}
Output: 1 3 2 4
Explanation: Perform the following swaps:
Swap A[1] and A[2], now A[] = { 3, 1, 2, 4 }
Swap A[0] and A[1], now A[] = { 1, 3, 2, 4 }
No further swaps are possible as A[1] and A[2] have already been swapped.
Input: A[] = { 2, 1, 4, 3, 6, 5 }
Output: 1 2 3 4 5 6
Explanation: Perform the following swaps:
Swap A[0] and A[1], now A[] = { 1, 2, 4, 3, 6, 5 }
Swap A[2] and A[3], now A[] = { 1, 2, 3, 4, 6, 5 }
Swap A[4] and A[5], now A[] = { 1, 2, 3, 4, 5, 6 }
Approach:
To solve the problem mentioned above we can apply Greedy method. We know that we can perform at most N – 1 swaps to make the given array as smallest as possible.
- Create a counter variable and initialize with N-1 and a hash-map to store performed swaps.
- Find the position of the minimum element from current index onward.
- Now perform swap backwards until we reach current element position.
- Also check if current swap is possible or not and decrement the counter also at each swap.
- Finally print the required array.
Below is the implementation of above approach:
C++
// C++ implementation to find the// lexicographically smallest// array by at most single swap// for every pair of adjacent indices#include <bits/stdc++.h>using namespace std;// Function to find the// lexicographically smallest arrayvoid findSmallestArray(int A[], int n){ // maximum swaps possible int count = n - 1; // hash to store swaps performed map<pair<int, int>, int> mp; for (int i = 0; i < n && count > 0; ++i) { // let current element be // the minimum possible int mn = A[i], pos = i; // Find actual position of // the minimum element for (int j = i + 1; j < n; ++j) { // Update minimum element and // its position if (A[j] < mn) { mn = A[j]; pos = j; } } // Perform swaps if possible while (pos > i && count > 0 && !mp[{ pos - 1, pos }]) { // Insert current swap in hash mp[{ pos - 1, pos }] = 1; swap(A[pos], A[pos - 1]); --pos; --count; } } // print the required array for (int i = 0; i < n; ++i) cout << A[i] << " ";}// Driver codeint main(){ int A[] = { 2, 1, 4, 3, 6, 5 }; int n = sizeof(A) / sizeof(A[0]); findSmallestArray(A, n); return 0;} |
Java
// Java implementation to find the// lexicographically smallest// array by at most single swap// for every pair of adjacent indicesimport java.util.*;class GFG { // Function to find the // lexicographically smallest array static void findSmallestArray(int[] A, int n) { // maximum swaps possible int count = n - 1; // hash to store swaps performed HashMap<String, Integer> mp = new HashMap<String, Integer>(); for (int i = 0; i < n && count > 0; ++i) { // let current element be // the minimum possible int mn = A[i]; int pos = i; // Find actual position of // the minimum element for (int j = i + 1; j < n; ++j) { // Update minimum element and // its position if (A[j] < mn) { mn = A[j]; pos = j; } } // Perform swaps if possible while (pos > i && count > 0 && !mp.containsKey( String.valueOf(pos - 1) + "#" + String.valueOf(pos))) { // Insert current swap in hash mp.put(String.valueOf(pos - 1) + "#" + String.valueOf(pos), 1); var temp = A[pos]; A[pos] = A[pos - 1]; A[pos - 1] = temp; --pos; --count; } } // print the required array for (int i = 0; i < n; ++i) System.out.print(A[i] + " "); } // Driver code public static void main(String[] args) { int[] A = { 2, 1, 4, 3, 6, 5 }; int n = A.length; findSmallestArray(A, n); }}// This code is contributed by phasing17. |
Python3
# Python3 implementation to find the# lexicographically smallest array by# at most single swap for every pair# of adjacent indices# Function to find the# lexicographically smallest arraydef findSmallestArray(A, n): # Maximum swaps possible count = n - 1 # Hash to store swaps performed mp = {''} for i in range(0, n): if(count <= 0): break; # Let current element be # the minimum possible mn = A[i] pos = i # Find actual position of # the minimum element for j in range(i + 1, n): # Update minimum element # and its position if (A[j] < mn): mn = A[j] pos = j # Perform swaps if possible while (pos > i and count > 0 and ((pos - 1, pos) not in mp)): # Insert current swap in hash mp.add((pos - 1, pos)) A[pos], A[pos - 1] = A[pos - 1], A[pos] pos -= 1 count -= 1 # Print the required array for i in range(0, n): print(A[i], end = " ")# Driver codeA = [ 2, 1, 4, 3, 6, 5 ]n = len(A)findSmallestArray(A, n)# This code is contributed by Sanjit_Prasad |
C#
// C# implementation to find the// lexicographically smallest// array by at most single swap// for every pair of adjacent indicesusing System;using System.Collections.Generic;class GFG { // Function to find the // lexicographically smallest array static void findSmallestArray(int[] A, int n) { // maximum swaps possible int count = n - 1; // hash to store swaps performed Dictionary<string, int> mp = new Dictionary<string, int>(); for (int i = 0; i < n && count > 0; ++i) { // let current element be // the minimum possible int mn = A[i]; int pos = i; // Find actual position of // the minimum element for (int j = i + 1; j < n; ++j) { // Update minimum element and // its position if (A[j] < mn) { mn = A[j]; pos = j; } } // Perform swaps if possible while (pos > i && count > 0 && !mp.ContainsKey( Convert.ToString(pos - 1) + "#" + Convert.ToString(pos))) { // Insert current swap in hash mp[Convert.ToString(pos - 1) + "#" + Convert.ToString(pos)] = 1; var temp = A[pos]; A[pos] = A[pos - 1]; A[pos - 1] = temp; --pos; --count; } } // print the required array for (int i = 0; i < n; ++i) Console.Write(A[i] + " "); } // Driver code public static void Main(string[] args) { int[] A = { 2, 1, 4, 3, 6, 5 }; int n = A.Length; findSmallestArray(A, n); }}// This code is contributed by phasing17. |
Javascript
// JS implementation to find the// lexicographically smallest// array by at most single swap// for every pair of adjacent indices// Function to find the// lexicographically smallest arrayfunction findSmallestArray(A, n){ // maximum swaps possible let count = n - 1; // hash to store swaps performed let mp = {}; for (var i = 0; i < n && count > 0; ++i) { // let current element be // the minimum possible var mn = A[i], pos = i; // Find actual position of // the minimum element for (var j = i + 1; j < n; ++j) { // Update minimum element and // its position if (A[j] < mn) { mn = A[j]; pos = j; } } // Perform swaps if possible while (pos > i && count > 0 && !mp.hasOwnProperty(pos - 1 + "#" + pos)) { // Insert current swap in hash mp[ pos - 1 + "#" + pos] = 1; var temp = A[pos]; A[pos] = A[pos - 1] A[pos - 1] = temp --pos; --count; } } // print the required array console.log(A.join(" ")) }// Driver codelet A = [ 2, 1, 4, 3, 6, 5 ];let n = A.length;findSmallestArray(A, n);// This code is contributed by phasing17 |
Output:
1 2 3 4 5 6
Time Complexity: O(N2)
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!
