# Use less memory and make it runs faster (if it is possible)

I have to improve this code that searches for missing and duplicates values in a list:

using System;
using System.Collections.Generic;

namespace Test
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Hello World!");

int[] input = new int[] { 5, 2, 1, 4, 6, 5 };

Tuple<List<int>, List<int>> result = Process(input);

Console.WriteLine("Missing values: ");

foreach (int value in result.Item1)
Console.WriteLine(value);

Console.WriteLine("Duplicate values: ");

foreach (int value in result.Item2)
Console.WriteLine(value);
}

static Tuple<List<int>, List<int>> Process(int[] input)
{
Dictionary<int, int> dict = new Dictionary<int, int>();
List<int> missing = new List<int>();
List<int> duplicate = new List<int>();

for(int index = 0; index < input.Length; index++)
{
int value = input[index];

if (dict.ContainsKey(value))
else
}

for(int index = 0; index< input.Length; index++)
{
int value = index + 1;

if (dict.ContainsKey(value))
continue;
else
}

return new Tuple<List<int>, List<int>>(missing, duplicate);
}
}
}


I have to use the less memory that I can and make it faster. I've been thinking about how to use only one for loop but I think I can't.

int[] input parameter can have n elements.

E.g. if n = 6, the input parameter should have { 1, 2, 3, 4, 5, 6} in any order.

How can I make it use less memory and runs faster?

• ericlippert.com/2012/12/17/performance-rant Nov 16, 2021 at 20:02
• The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question? for examples, and revise the title accordingly. Nov 16, 2021 at 20:15
• my only concern is the missing part, because you're using the array length, which would invalidate the results if the element value is larger than the array length.
– iSR5
Nov 16, 2021 at 21:26
• Recursion. Take the leading input pair and recurse with the remaining. Have each recursive call run on a different cpu core using C#'s parallel programming model. I suspect that presorting the input array is not necessarily required. The general idea reminds me of the quicksort algorithm. Nov 16, 2021 at 22:08
• The code doesn't work correctly. Calling Process with input {2,5} returns missing value 1. Nov 17, 2021 at 8:51

### Review

Use proper types. If you don't need to map values to something else, you don't need Dictionary. You should use a HashSet here.

### Better performance

I don't think you can do better than $$\O(n)\$$ speed here. But you can avoid creating extra structures (and save memory). It looks like you should do something like sorting here, so it would be a good idea to recall sorting algorithms... and BUM! - counting sort looks very close to what you need. Create an array (List) of 0's and increase every element taking input array as indexes (minus 1 to be precise). Now, to get missing elements, walk that array and gather indexes of 0's. To get duplicates - walk it and gather indexes of numbers greater than 1. If the task doesn't tell you to form a tuple, you can do that in output loops. Also check the exact task - do you need to find duplicates or duplicate values? I.e. does {2, 2, 2} have 3 duplicates of 2 or only 1 duplicate with value of 2 (repeated 3 times)? In the second case you can save even more memory by using BitArray to store counts.

• Thanks for your answer. I use a dictionary because it lets me search for a value. And, yes, I thought to use a HashSet. Thanks again. Nov 17, 2021 at 11:11
• You're using only Add and ContainsKey methods. HashSet has Add and Contains. Nov 17, 2021 at 17:27

From an $$\O(n)\$$ perspective, the code is already pretty fast. Everything in the loops is constant or amortized constant.

So let's look at memory. Allocating the dictionary is something we can remove, the lists belong to the return and cannot be removed.

Therefore you could sort the input array first $$\(O(n*log n))\$$ and then loop over it once to add elements into the list. Start with the first element and look at the next one to decide which list needs an addition.

if the element is the same as the last element
check whether it is the last added duplicate (if not: add it)
else
all elements in between are missing, add them to the missing list


Reading your suggestions, especially from Pavlo Slavynskyy I have updated the method:

static Tuple<BitArray, BitArray> Process2(int[] input)
{
HashSet<int> set = new HashSet<int>();
BitArray missing = new BitArray(input.Length, true);
BitArray repeated = new BitArray(input.Length, false);

for(int index = 0; index < input.Length; index++)
{
int value = input[index] - 1;

// This value is not missing.
missing[value] = false;

if (set.Contains(value))
repeated[value] = true;
else