Searching the same values in an array

Question

If I am not mistaken, this method has a complexity \$O(N^2)\$:

int[] exampleArray = { 4, 6, 2, 2, 6, 6, 1, 55, 55, 2, 5, 6, 90, 8, 8, 8, 10, 70 };
int k = GetMaximumCycle(exampleArray);

public static int GetMaximumCycle(int[] anArray)
{
   int length = anArray.Length;
   int result = 0;
   for (int i = 0; i < length; i++)
   {
      for (int j = 0; j < length; j++)
      {
          if (anArray[i] == anArray[j])
          {
             if (!(result > Math.Abs(i - j)))                            
                 result = Math.Abs(i - j);
          }                    
      }                
   }
   return result;
}

I compare values and gets the maximum difference between items of array. The result variable is 10.

And if an input array is very large, this code works slowly. Is it possible to simplify the for loops or remove the second for loop to have a complexity of \$O(N)\$?

Answer 1

You can use a Dictionary<int, int> of positions of the first occurrence of each element value. Next, iterating over all elements of the input array, you do:

• If the positions[value] is empty, store the current index i in it: positions[value] = i.
• Else, calculate the distance (or cycle length).
• If this distance is greater than maximum, save it as a new maximum.

This algorithm has time complexity \$O(n)\$.

The code:

public static class CycleSearch
{
    public static int GetMaximumCycle(int[] array)
    {
        Dictionary<int, int> positions = new Dictionary<int, int>();

        int result = 0;
        for (int i = 0; i < array.Length; i++)
        {
            int value = array[i];
            int position;
            if (!positions.TryGetValue(value, out position))
            {
                positions[value] = i;
            }
            else
            {
                int cycleLength = i - position;
                if (cycleLength > result)
                {
                    result = cycleLength;
                }
            }
        }
        return result;
    }
}

Usage:

int[] exampleArray = { 4, 6, 2, 2, 6, 6, 1, 55, 55, 2, 5, 6, 90, 8, 8, 8, 10, 70 };
Console.WriteLine(CycleSearch.GetMaximumCycle(exampleArray));

Output:

10

Answer 2

There is no real reason why your method should be restricted to array and int. You can make it easily generic (the below code is based on @Dmitry`s answer):

    public static class CycleSearch
    {
        public static int GetMaximumCycle<T>(IEnumerable<T> sequence)
        {
            var positions = new Dictionary<T, int>();

            int result = 0;
            int index = 0;
            foreach (var value in sequence)
            {
                int position;
                if (!positions.TryGetValue(value, out position))
                {
                    positions[value] = index;
                }
                else
                {
                    int cycleLength = index - position;
                    if (cycleLength > result)
                    {
                        result = cycleLength;
                    }
                }
                index += 1;
            }
            return result;
        }
    }

Answer 3

You are correct, it is \$O(n^2)\$.

I seriously doubt it is possible to reduce time complexity to \$O(n)\$, however there is a solution with \$O(n\log n)\$ time and \$O(n)\$ space complexity: sort the set of (value, index) pairs, and obtain the result in a single linear pass.