Data Modelling & AI Data Structure & Algorithm

Lexicographically smallest permutation with distinct elements using minimum replacements

23 June 2025

1

Given an array of n positive integers such that each element of an integer is from 1 to n. Find the lexicographically permutation that can be obtained by replacing minimum number of elements in array such that every element of array occurs exactly once in the entire array. First, print the minimum number of replacements required and then print the final lexicographical array.

Examples:

Input arr[] = {2, 3, 4, 3, 2}
Output 2
           1 3 4 5 2
Explanation
Replace number '2' at position 1^st with number 
'1' and '3' at position 4^th with number '5'. 
The array that we obtain is [1, 3, 4, 5, 2]
which is lexicographically smallest among all 
the possible suitable.

Input arr[] = {2, 1, 2, 1, 2}
Output 3
           2 1 3 4 5

Naive approach is to generate all the permutation from 1 to n and pick the smallest one which renders the minimum replacements. Time complexity of this approach is O(n!) which will definitely time out for a large value of n.

Efficient approach is to pick desired elements greedily. Firstly initialize the cnt[] array which will contain the frequency of elements occurring in the array. For each element of array(a_i), occurred more than once in an array, add the numbers in ascending order because of getting lexicographically minimal permutation. For instance,
Iterate the array over all elements. Let the current number of array is a_i. If count of a_i is equaled to 1 then move to the next number of array. If count of a_i is greater than 1 then replace the number a_i with element ele(the smallest number which does not occur in array) only if ele < a_i. Meanwhile, decrease the count of a_i in cnt[] array.
If ele > a_i then mark the number a_i so that we can replace it in the next iteration. This step this need because we need to make smallest lexicographically permutation.

For example, let's suppose the arr[] = {1, 5, 4, 5, 3, 7, 3} 

In first iteration '5' occurs two times in array(indexing 1), 
therefore we have to replace '5' at position '2' with '2'(2 < 5). 
Now the updated array = {1, 2, 4, 5, 3, 7, 3} 

In next iteration, '3' would be consider as it occurs two times 
in array. But this time the next element of replacement would 
be equals to 6 which is greater than 3. Therefore visit element 
3 in boolean array vis[] and iterate over other elements. 
Now again '3' occurred at position 7^th, this time replace it with 
number '6'. 
Final array is arr[] = {1, 2, 4, 5, 3, 7, 6}

Implementation:

C++

// C++ program to print lexicographically 
// permutation array by replacing minimum 
// element of array 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to calculate lexicographically permutation 
// in array 
void lexicoSmallestPermuatation(int arr[], int n) 
{ 
    // Calculate frequency of array elements 
    int cnt[n + 1]; 
    memset(cnt, 0, sizeof(cnt)); 
    for (int i = 0; i < n; ++i) 
        ++cnt[arr[i]]; 
  
    int ele = 1, replacement = 0; 
    bool vis[n + 1]; 
    memset(vis, 0, sizeof(vis)); 
    for (int i = 0; i < n; ++i) { 
  
        // If count of element is 1, no 
        // need to replace 
        if (cnt[arr[i]] == 1) 
            continue; 
  
        // Find the element that has not 
        // occurred in array 
        while (cnt[ele]) 
            ++ele; 
  
        // If replacement element is greater 
        // than current arr[i] then visit 
        // that element for next iteration 
        if (ele > arr[i] && !vis[arr[i]]) 
            vis[arr[i]] = 1; 
  
        else { 
  
            // Decrement count and assign the element 
            // to array 
            --cnt[arr[i]]; 
            arr[i] = ele; 
  
            // Increment the replacement count 
            ++replacement; 
  
            // Increment element after assigning 
            // to the array 
            ++ele; 
        } 
    } 
  
    cout << replacement << "\n"; 
    for (int i = 0; i < n; ++i) 
        cout << arr[i] << " "; 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { 2, 3, 4, 3, 2 }; 
    int sz = sizeof(arr) / sizeof(arr[0]); 
    lexicoSmallestPermuatation(arr, sz); 
    return 0; 
} 

Java

// Java program to print lexicographically 
// permutation array by replacing minimum 
// element of array 
  
class GFG { 
  
// Function to calculate lexicographically permutation 
// in array 
    static void lexicoSmallestPermuatation(int arr[], int n) { 
        // Calculate frequency of array elements 
        int cnt[] = new int[n + 1]; 
        for (int i = 0; i < n; ++i) { 
            ++cnt[arr[i]]; 
        } 
  
        int ele = 1, replacement = 0; 
        boolean vis[] = new boolean[n + 1]; 
        for (int i = 0; i < n; ++i) { 
  
            // If count of element is 1, no 
            // need to replace 
            if (cnt[arr[i]] == 1) { 
                continue; 
            } 
  
            // Find the element that has not 
            // occurred in array 
            while (cnt[ele]>0) { 
                ++ele; 
            } 
  
            // If replacement element is greater 
            // than current arr[i] then visit 
            // that element for next iteration 
            if (ele > arr[i] && !vis[arr[i]]) { 
                vis[arr[i]] = true; 
            } else { 
  
                // Decrement count and assign the element 
                // to array 
                --cnt[arr[i]]; 
                arr[i] = ele; 
  
                // Increment the replacement count 
                ++replacement; 
  
                // Increment element after assigning 
                // to the array 
                ++ele; 
            } 
        } 
  
        System.out.print(replacement + "\n"); 
        for (int i = 0; i < n; ++i) { 
            System.out.print(arr[i] + " "); 
        } 
    } 
  
// Driver code 
    public static void main(String[] args) { 
        int arr[] = {2, 3, 4, 3, 2}; 
        int sz = arr.length; 
        lexicoSmallestPermuatation(arr, sz); 
  
    } 
}  
  
// This code is contributed by 29AjayKumar 

Python3

# Python 3 program to print lexicographically 
# permutation array by replacing minimum 
# element of array 
  
# Function to calculate lexicographically  
# permutation in array 
def lexicoSmallestPermuatation(arr, n): 
      
    # Calculate frequency of array elements 
    cnt = [0 for i in range(n + 1)] 
    for i in range(n): 
        cnt[arr[i]] += 1
  
    ele = 1
    replacement = 0
    vis = [0 for i in range(n + 1)] 
    for i in range(n): 
          
        # If count of element is 1, no 
        # need to replace 
        if (cnt[arr[i]] == 1): 
            continue
  
        # Find the element that has not 
        # occurred in array 
        while (cnt[ele]): 
            ele += 1
  
        # If replacement element is greater 
        # than current arr[i] then visit 
        # that element for next iteration 
        if (ele > arr[i] and vis[arr[i]] == 0): 
            vis[arr[i]] = 1; 
  
        else: 
              
            # Decrement count and assign  
            # the element to array 
            cnt[arr[i]] -= 1
            arr[i] = ele 
  
            # Increment the replacement count 
            replacement += 1
  
            # Increment element after assigning 
            # to the array 
            ele += 1
      
    print(replacement) 
    for i in range(n): 
        print(arr[i], end = " ") 
  
# Driver code 
if __name__ == '__main__': 
    arr = [2, 3, 4, 3, 2] 
    sz = len(arr) 
    lexicoSmallestPermuatation(arr, sz) 
      
# This code is contributed by 
# Shashank_Sharma 

C#

      
// C# program to print lexicographically  
// permutation array by replacing minimum  
// element of array   
using System; 
public class GFG {  
  
// Function to calculate lexicographically permutation  
// in array  
    static void lexicoSmallestPermuatation(int []arr, int n) {  
        // Calculate frequency of array elements  
        int []cnt= new int[n + 1];  
        for (int i = 0; i < n; ++i) {  
            ++cnt[arr[i]];  
        }  
  
        int ele = 1, replacement = 0;  
        bool []vis = new bool[n + 1];  
        for (int i = 0; i < n; ++i) {  
  
            // If count of element is 1, no  
            // need to replace  
            if (cnt[arr[i]] == 1) {  
                continue;  
            }  
  
            // Find the element that has not  
            // occurred in array  
            while (cnt[ele]>0) {  
                ++ele;  
            }  
  
            // If replacement element is greater  
            // than current arr[i] then visit  
            // that element for next iteration  
            if (ele > arr[i] && !vis[arr[i]]) {  
                vis[arr[i]] = true;  
            } else {  
  
                // Decrement count and assign the element  
                // to array  
                --cnt[arr[i]];  
                arr[i] = ele;  
  
                // Increment the replacement count  
                ++replacement;  
  
                // Increment element after assigning  
                // to the array  
                ++ele;  
            }  
        }  
  
        Console.Write(replacement + "\n");  
        for (int i = 0; i < n; ++i) {  
            Console.Write(arr[i] + " ");  
        }  
    }  
  
// Driver code  
    public static void Main() {  
        int []arr = {2, 3, 4, 3, 2};  
        int sz = arr.Length;  
        lexicoSmallestPermuatation(arr, sz);  
  
    }  
}  
  
// This code is contributed by Rajput-Ji// 

PHP

<?php  
// PHP program to print lexicographically 
// permutation array by replacing minimum 
// element of array 
  
// Function to calculate lexicographically  
// permutation in array 
function lexicoSmallestPermuatation(&$arr, $n) 
{ 
    // Calculate frequency of array elements 
    $cnt = array_fill(0, $n + 1, NULL); 
    for ($i = 0; $i < $n; ++$i) 
        ++$cnt[$arr[$i]]; 
  
    $ele = 1; 
    $replacement = 0; 
    $vis = array_fill(0, $n + 1, NULL); 
    for ($i = 0; $i < $n; ++$i)  
    { 
  
        // If count of element is 1, no 
        // need to replace 
        if ($cnt[$arr[$i]] == 1) 
            continue; 
  
        // Find the element that has not 
        // occurred in array 
        while ($cnt[$ele]) 
            ++$ele; 
  
        // If replacement element is greater 
        // than current arr[i] then visit 
        // that element for next iteration 
        if ($ele > $arr[$i] && !$vis[$arr[$i]]) 
            $vis[$arr[$i]] = 1; 
  
        else 
        { 
  
            // Decrement count and assign the  
            // element to array 
            --$cnt[$arr[$i]]; 
            $arr[$i] = $ele; 
  
            // Increment the replacement count 
            ++$replacement; 
  
            // Increment element after assigning 
            // to the array 
            ++$ele; 
        } 
    } 
  
    echo $replacement. "\n"; 
    for ($i = 0; $i < $n; ++$i) 
        echo $arr[$i] . " "; 
} 
  
// Driver code 
$arr = array(2, 3, 4, 3, 2 ); 
$sz = sizeof($arr); 
lexicoSmallestPermuatation($arr, $sz); 
  
// This code is contributed by ita_c 
?> 

Javascript

<script> 
  
// Javascript program to 
// print lexicographically 
// permutation array by  
// replacing minimum 
// element of array 
  
// Function to calculate  
// lexicographically permutation 
// in array 
    function lexicoSmallestPermuatation(arr, n)  
    { 
        // Calculate frequency of  
        // array elements 
        let cnt = Array.from({length: n + 1}, 
                 (_, i) => 0); 
        for (let i = 0; i < n; ++i) 
        { 
            ++cnt[arr[i]]; 
        } 
    
        let ele = 1, replacement = 0; 
        let vis = Array.from({length: n + 1},  
                  (_, i) => 0); 
        for (let i = 0; i < n; ++i) { 
    
            // If count of element is 1, no 
            // need to replace 
            if (cnt[arr[i]] == 1) { 
                continue; 
            } 
    
            // Find the element that has not 
            // occurred in array 
            while (cnt[ele]>0) { 
                ++ele; 
            } 
    
            // If replacement element is greater 
            // than current arr[i] then visit 
            // that element for next iteration 
            if (ele > arr[i] && !vis[arr[i]]) { 
                vis[arr[i]] = true; 
            } else { 
    
                // Decrement count and 
                // assign the element 
                // to array 
                --cnt[arr[i]]; 
                arr[i] = ele; 
    
                // Increment the 
                // replacement count 
                ++replacement; 
    
                // Increment element  
                // after assigning 
                // to the array 
                ++ele; 
            } 
        } 
    
        document.write(replacement + "<br/>"); 
        for (let i = 0; i < n; ++i) { 
            document.write(arr[i] + " "); 
        } 
    } 
  
// driver program  
  
        let arr = [2, 3, 4, 3, 2]; 
        let sz = arr.length; 
        lexicoSmallestPermuatation(arr, sz); 
    
</script> 

Output

2
1 3 4 5 2

Time complexity: O(n)

This article is contributed by Shubham Bansal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

2 COMMENTS

cat888 14 December 2025 At 8:12 am

… [Trackback]

[…] Read More here to that Topic: geeksforgeeks.org/lexicographically-smallest-permutation-with-distinct-elements-using-minimum-replacements/ […]

Log in to leave a comment
z16 21 December 2025 At 3:05 pm

… [Trackback]

[…] Read More here on that Topic: geeksforgeeks.org/lexicographically-smallest-permutation-with-distinct-elements-using-minimum-replacements/ […]

Log in to leave a comment

Lexicographically smallest permutation with distinct elements using minimum replacements

C++

Java

Python3

C#

PHP

Javascript

Adding Persistent Memory to Claude Code with the Lightweight memsearch Plugin

GLM-5 vs. MiniMax M2.5 vs. Gemini 3 Deep Think: Which Model Fits Your AI Agent Stack?

We Extracted OpenClaw’s Memory System and Open-Sourced It (memsearch)

2 COMMENTS

LEAVE A REPLY Cancel reply

Most Popular

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

Samsung’s June update brings Galaxy S25 three powerful AI tricks the S26 already had

EDITOR PICKS

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

POPULAR POSTS

Google Photos could be working on new ways to transform your videos

The two most extreme phones ever. [Video]

What to watch this weekend: You can Outlast: The Jungle or try Surviving Earth

POPULAR CATEGORY

ABOUT US

FOLLOW US