-1
\$\begingroup\$

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))
                    duplicate.Add(value);
                else
                    dict.Add(value, value);
            }

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

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

            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?

\$\endgroup\$
7
  • 1
    \$\begingroup\$ ericlippert.com/2012/12/17/performance-rant \$\endgroup\$ Nov 16 '21 at 20:02
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – Martin R
    Nov 16 '21 at 20:15
  • \$\begingroup\$ 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. \$\endgroup\$
    – iSR5
    Nov 16 '21 at 21:26
  • \$\begingroup\$ 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. \$\endgroup\$
    – radarbob
    Nov 16 '21 at 22:08
  • 1
    \$\begingroup\$ The code doesn't work correctly. Calling Process with input {2,5} returns missing value 1. \$\endgroup\$
    – raznagul
    Nov 17 '21 at 8:51
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – VansFannel
    Nov 17 '21 at 11:11
  • \$\begingroup\$ You're using only Add and ContainsKey methods. HashSet has Add and Contains. \$\endgroup\$ Nov 17 '21 at 17:27
6
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
            set.Add(value);
    }

    return new Tuple<BitArray, BitArray>(missing, repeated);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.