Add index to duplicate entry in List<T>

Question

I wrote this piece of code to append index to any duplicate entry in List<T> like in the sample below.

Input

["dupe", "not dupe", "dupe", "also not dupe"]

Output

["dupe1", "not dupe", "dupe2", "also not dupe"]

But the problem is it's O(n^2) in the second loop and I'm working on a large list (30+ items). I'm very new to C# and didn't know much built-in functions, so I wanted to know is there anything I can do to optimize this?

List<string> duplicate = new List<string>(); // For storing duplicate item
IEnumerable<IGrouping<string, string>> g = header.GroupBy(i => i);

// Find duplicate and store it in duplicate
foreach (var item in g)
    if (item.Count() > 1)
        duplicate.Add(item.Key);

// Loop through duplicate to append the index
foreach (var item in duplicate) {
    int start = 1;
    for (int i = 0; i < header.Count; i++) {
        // If header[i] is a duplicate item append index to it.
        if (string.Equals(header[i], item, StringComparison.OrdinalIgnoreCase)) {
            header[i] = string.Format("{0}{1}", header[i], start);
            start++;
        }
    }
}

Answer 1

If you collect the indices along with the duplicates, you don't need to loop over the list again:

var header = new List<string>();
var duplicates = header.Select((x, index) => new { x, index }).ToLookup(x => x.x, x => x.index);
foreach(var duplicate in duplicates.Where(x => x.Count() > 1)) {
  var start = 1;
  foreach(var index in duplicate) {
    header[index] = $"{duplicate.Key}{start++}";
  }
}

This uses string interpolation ($-strings) as a shorthand for string.Format.

---

On premature optimisation:

You seem concerned about the \$O(n^2)\$ performance of your solution. At the same time you mention your actual input will have ~30 items. Before spending too much time worrying about the efficiency of your code, did you try to find out whether your current solution is problematic? It seems to me that the list is small enough that even a less efficient solution should be quick enough.

Before trying to optimise specific parts of your code, ask yourself two things:

1. Do I need to optimise? Is execution time currently a problem?
2. Where is the efficiency problem in the code?

Before optimising, profile your program to figure out where the problems actually are. Before that, efficiencies like \$O(n^2)\$ or \$O(n \log n)\$ are purely academic.

Answer 2

Here is way where you can preserve the order, and you only iterate twice (including duplicated iteration`):

var duplicated = header
                .GroupBy(x => x)
                .Where(x => x.Count() > 1)
                .ToDictionary(x => x.Key, x => 0);

for (int i = 0; i < header.Length; i++)
{
    if (duplicated.TryGetValue(header[i], out int value))
    {
        value++;
        duplicated[header[i]] = value;
        header[i] = $"{header[i]}{value}";
    }
}

Answer 3

If you do not explicitly need the first dupe to be renamed to dupe1 then you can use:

List<string> input = new List<string>() { "dupe", "not dupe", "dupe", "also not dupe" };
List<string> output = new List<string>();

Dictionary<string, int> duplicates = new Dictionary<string, int>();

foreach (string item in input)
{
    string value = item;
    if (!duplicates.ContainsKey(item))
    {
        duplicates.Add(item, 0);
    }
    else
    {
        duplicates[item]++;
        value += duplicates[item];
    }

    output.Add(value);
}

If starting with dupe1 is important, then you can use a lookahead, like this:

List<string> input = new List<string>() { "dupe", "not dupe", "dupe", "also not dupe" };
List<string> output = new List<string>();

Dictionary<string, int> duplicates = new Dictionary<string, int>();

int index = 0;
foreach (string item in input)
{
    string value = item;

    if (input.IndexOf(item, index + 1) >= 0)
    {
        value += "1";
    }

    if (!duplicates.ContainsKey(item))
    {
        duplicates.Add(item, 1);
    }
    else
    {
        duplicates[item]++;
        value += duplicates[item];
    }

    output.Add(value);
    index++;
}
```