Lexicographically smallest array formed by at most one swap for every pair of adjacent indices

0 0 6 minutes read

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:

$0 <= K < N-1$

, 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 array
void 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 code
int 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 indices
import 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 array
def 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 code
A = [ 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 indices
using 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 array
function 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 code
let 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(N²)

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 zambiatek!