Given a sorted list of integers that may contain duplicates, what would be an efficient algorithm to ensure all integers are unique and the list is still sorted with the minimum number of edits. One could take a greedy approach, but that won’t result in the minimum number of edits.

For example, given the list [0,1,1,1,2,3,4],

[-2,-1,0,1,2,3,4] requires less edits than [0,1,2,3,4,5,6].

Given the list [0,1,1,3,4], [0,1,2,3,4] would be the most efficient.

It seems like this can’t be done in linear time.

Insertion sort is a simple sorting algorithm, it builds the final sorted array one item at a time.

Note: It is much less efficient on large lists than other sort algorithms.

Insertion sort iterates through the list by consuming one input element at each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Consider the given code:

public class Main { public static void main(String[] args) { int[] arr1 = {0,1,1,1,7,6,7,88,42}; int[] arr2 = doInsertionSort(arr1); for(int i:arr2){ System.out.print(i); System.out.print(", "); } } public static int[] doInsertionSort(int[] input){ int temp; for (int i = 1; i < input.length; i++) { for(int j = i ; j > 0 ; j--){ if(input[j] < input[j-1]){ temp = input[j]; input[j] = input[j-1]; input[j-1] = temp; } } } return input; } }

I hope it would help. Thanks!